enakai00 https://blog.hatena.ne.jp/enakai00/ めもめも https://enakai00.hatenablog.com/ 何の話かと言うと atcoder.jpこの問題をネタに「重み0のリンクで結合されたノードを同一視する」という話をします。 一般的な解法 まず、この問題の一般的な解法は、01-BFS になります。方向転換を考慮する必要があるので、座標 (x, y) + 方向（上下方向 or 左右方向）をノードとします。たとえば、・(1, 1, '|') : 座標 (1, 1) を上下方向に移動中 ・(1, 1, '-') : 座標 (1, 1) を左右方向に移動中という感じです。そして、これらのノードをリンクで結合します。座標を変えずに方向だけ変えるリンクを重み 1 とします。・(1, 1, '|') (1, … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fenakai00.hatenablog.com%2Fentry%2F2021%2F08%2F14%2F145139" title="043 - Maze Challenge with Lack of Sleep（★4）の解説 - めもめも" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-08-14 14:51:39 rich https://enakai00.hatenablog.com/entry/2021/08/14/145139 1.0 100%