(略解です。正式な解説は後日公開されます。)

グリッドグラフのうち . に対応する辺を縮約して # に対応する辺を貼らないグラフ \(G\) を考えます。任意の辺は D, A , B のいずれかに対応します。
\((1,1)\) に対応する頂点を \(S\), \((N, N)\) に対応する頂点を \(T\) と置きます。\(G\) が連結成分を \(1\) 個だけ持ち \(S\) と \(T\) が連結である場合が解ければよいです。

求めたいものは D 辺の集合 \(X\) であって以下の条件を満たすものを 良い集合 と呼びます:

• \(G - X\) では \(S,T\) は連結
• \(G - X - \lbrace A \rbrace\) でも \(S,T\) は連結
• \(G - X - \lbrace B \rbrace\) でも \(S,T\) は連結
• \(G - X - \lbrace A, B \rbrace\) では \(S,T\) は非連結

求めたいものは良い集合 \(X\) の最小サイズです。
ここで次の命題が成り立ちます：

D 辺の集合 \(X\) について次の 2 個の命題は同値である：

1. \(X\) が極小な良い集合である。
2. \(X\) が \(X \cup \lbrace A,B\rbrace\) が極小な \(S-T\) カットである。

(証明) \(1 \to 2\) : 極小な良い集合を \(1\) 個取り \(X\) とする。\(H = G - X - \lbrace A, B \rbrace\) とする。\(H\) において \(S\) を含む連結成分を \(V_1\), \(T\) を含む連結成分を \(V_2\) とする。
まず、良い集合の条件より、明らかに \(A, B\) は \(V_1\) と \(V_2\) をまたぐ辺である。
また、\(H\) は \(V_1, V_2\) の \(2\) 個のみを連結成分として持つとしてよい。(もしそうでなければ少なくとも一方の端点を \(V_1, V_2\) 以外に持つ辺を \(X\) に含み、そのような辺を取り除くことが可能であり最小性に反する。)
したがって \(X \cup \lbrace A,B\rbrace\) は \(V_1, V_2\) をまたぐ辺全体となっているため極小な \(S-T\) カットとなる。
\(2 \to 1\) : \(X \cup \lbrace A,B\rbrace\) が極小な \(S-T\) カットである時に \(X\) が極小な良い集合であることを確認すればよく、これは容易である。 (証明終わり)

よって \(X \cup \lbrace A,B\rbrace\) が極小な \(S-T\) カットであるような \(X\) の最小サイズを求めればよいです。

平面グラフの性質から、極小な \(S-T\) カットは双対グラフの単純閉路に対応します。特に今回の問題では適切に双対グラフ上に超頂点 \(S', T'\) を追加することで特定の頂点を通る最短パスを求める問題に帰着されます。
帰着先の問題は標数 2 の体を用いた DP で多項式時間で解けることが知られています。 論文 計算量は \(\mathrm{O}(N^4)\) 程度で十分高速です。