[Codeforces] Codeforces Round #676 (Div. 2) B. Putting Bricks in the Wall

問題

方針

どのような状態だと ‘S’ から ‘F’ に行くことができないかを考えます。マス \( (i, j) \) の数字を \( c(i, j) \) とします。ただし、\( c(1, 1) = S \)、\( c(n, n) = F\) です。題意を満たすマスの状態は次の \( 2 \) つの条件のどれかを満たせば十分です。

\begin{eqnarray}
c(1, 2) &=& 1\\
c(2, 1) &=& 1 \\
c(n, n-1) &=& 0\\
c(n-1, n) &=& 0
\end{eqnarray}

または、

\begin{eqnarray}
c(1, 2) &=& 0\\
c(2, 1) &=& 0 \\
c(n, n-1) &=& 1\\
c(n-1, n) &=& 1
\end{eqnarray}

したがって、上記の条件を探索します。

コード

感想

連結しているマスとかを考えてドツボに嵌りました。