グリッドと行列

二次元のグリッドを渡されて、その上を探索する問題はよく出てきます。Number of Islands や Rotting Oranges がその例です。各マスを最大 4 つの隣を持つ頂点と考えれば、おなじみの探索手法がそのまま使えます。

4 つの章は、グリッド上の DFS、グリッド上の BFS、移動コストが 0 か 1 のときに使う 0-1 BFS、そしてそれらを組み合わせた問題です。短めの問題集で、ルート上では木とグラフアルゴリズムの間に位置します。