F - Unpredictable Moves Editorial by evima

Intended wrong solution

Can it be solved with 01-BFS where cost $1$ is incurred when entering a wall cell and when going straight through a cell with walls on both sides?
→ It reports $3$ for the following case. (The correct answer is $2$)

..#...
......
####..
......
..####
......
...#..

Solution

Adding (unbreakable) walls on the outside as follows does not change the answer.

..XXXXXX
...#...X
X......X
X####..X
X......X
X..####X
X......X
X...#...
XXXXXX..

Consider a graph (hereafter called the wall graph) where edges are added between pairs of walls with distance $1$ (vertically or horizontally adjacent), $\sqrt{2}$ (diagonally adjacent), or $2$ (relation of #.#).

Then, the following holds:

Being able to reach $(H,W)$ from $(1,1)$ without destroying walls is equivalent to the non-existence of a path from top-right to bottom-left in the wall graph.

Brief proof

Consider a graph (hereafter called the path graph) where vertices are the centers of each edge of the grid, and for grid edges $a,b$, an edge is added connecting the vertices corresponding to $a,b$ if edge $b$ can be passed immediately after passing edge $a$. We can reach $(H,W)$ from $(1,1)$ without destroying walls if and only if there exists a path from a top-left vertex (a vertex corresponding to one of the four edges of the top-left cell) to a bottom-right vertex in the path graph.

Then, exactly one of "the top-left vertex and bottom-right vertex are connected in the path graph" and "the top-right vertex and bottom-left vertex are connected in the wall graph" is satisfied.

One is disconnected: This is shown from the fact that a path in the path graph and a path in the wall graph cannot intersect.
One is connected: A path can be created by tracing the perimeter of the connected component of the disconnected one.

In other words, the answer is the minimum number of walls to delete to disconnect the top-right and bottom-left of the wall graph. This can be computed by mincut (maxflow).
The maximum flow is $O(H+W)$, so the complexity is $O((H+W)HW)$.

How to construct the mincut graph

Split each wall vertex $v$ into two vertices connected by one edge $v_{\mathrm{in}} \to v_{\mathrm{out}}$ (capacity $1$), make other edges capacity $\infty$, and compute the minimum $s$-$t$ cut using a maximum flow algorithm.

For the outer walls, merge the top-right and bottom-left into one vertex each, let the $v_{\mathrm{out}}$ of the top-right be $s$, and the $v_{\mathrm{in}}$ of the bottom-left be $t$. The edges to add are as follows:

For each wall vertex $v$, edge $v_{\mathrm{in}} \to v_{\mathrm{out}}$ (capacity $1$)
For adjacent vertices $u,v$ in the wall graph, edge $u_{\mathrm{out}} \to v_{\mathrm{in}}$ (capacity $\infty$)

posted:
last update: