公式解説とは異なるグラフを構築する解法をご紹介します。（追記: これは 054 - Takahashi Number（★6） の想定解法と同じ解法のようです。）

元のグリッドグラフで一手で上下左右のどれかの方向に好きなだけ進めるとしたときの最短路長を \(d\) として、出力すべき量は \(d / 2 - 1\) です。この \(d\) は元のグリッドグラフを次のように拡張したグラフにおける最短路長と等しいです。

• \(s _ {i, l} , \dots, s _ {i, r - 1} = \mathtt { '.' }\) なる \(i, l, r\) であって、 これを満たす中で区間 \(\lbrack l, r \lbrack\) が極大であるものすべてに対して、新しい頂点を追加し、それと頂点 \((i, l) , \dots, (i, r - 1)\) を結びます。
• \(s _ {l, j} , \dots, s _ {r - 1, j} = \mathtt { '.' }\) なる \(l, r, j\) であって、 これを満たす中で区間 \(\lbrack l, r \lbrack\) が極大であるものすべてに対して、新しい頂点を追加し、それと頂点 \((l, j) , \dots, (r - 1, j)\) を結びます。

提出 (273 ms): https://atcoder.jp/contests/typical90/submissions/28324273