マス目の各辺の中心を頂点とし、マス目の辺 $a,b$ について、$a$ を通過した直後に $b$ を通過できるときに $a,b$ に対応する頂点を結ぶ辺を張ったグラフ（以下、道グラフと呼びます）を考えます。道グラフにおいて左上の頂点（左上のマスの $4$ 辺のうちのいずれかに対応する頂点）から右下の頂点へパスが存在する時に限り、壁を壊さずに $(1,1)$ から $(H,W)$ に到達できます。

このとき、「道グラフの左上の頂点と右下の頂点が連結」または「壁グラフの右上の頂点と左下の頂点が連結」のうちちょうど一方のみが満たされます。

• どちらかは非連結：道グラフの経路と壁グラフの経路は交差不可であることから示されます。
• どちらかは連結：非連結な方の連結成分の外周を辿ることで経路を作ることが出来ます。

各壁頂点 $v$ を $v_{\mathrm{in}} \to v_{\mathrm{out}}$ の $1$ 本の辺（容量 $1$）で繋がれた $2$ つの頂点に分け、他の辺を容量 $\infty$ にした最小 $s$-$t$ カットとして、最大流のアルゴリズムで求められます。

外壁は右上と左下で $1$ 頂点にまとめ、右上の $v_{\mathrm{out}}$ を $s$、左下の $v_{\mathrm{in}}$ を $t$ とします。張る辺は以下の通りです。

• 各壁頂点 $v$ について辺 $v_{\mathrm{in}} \to v_{\mathrm{out}}$（容量 $1$）
• 壁グラフで隣接する頂点 $u,v$ に対して、辺 $u_{\mathrm{out}} \to v_{\mathrm{in}}$（容量 $\infty$）