[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}
したがって、上記の条件を探索します。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n; string s[200]; int cost(char c1, char c2) { int ret = 0; if (c1 != s[0][1]) ret++; if (c1 != s[1][0]) ret++; if (c2 != s[n - 1][n - 2]) ret++; if (c2 != s[n - 2][n - 1]) ret++; return ret; } void print(char c1, char c2) { if (c1 != s[0][1]) cout << "1 2\n"; if (c1 != s[1][0]) cout << "2 1\n"; if (c2 != s[n - 1][n - 2]) cout << n << " " << n - 1 << "\n"; if (c2 != s[n - 2][n - 1]) cout << n - 1 << " " << n << "\n"; } void solve() { if (cost('1', '0') <= 2) { cout << cost('1', '0') << "\n"; print('1', '0'); } else { cout << cost('0', '1') << "\n"; print('0', '1'); } } int main() { int t; cin >> t; for (int i = 0; i < t; i++) { cin >> n; for (int j = 0; j < n; j++) { cin >> s[j]; } solve(); } return 0; }
感想
連結しているマスとかを考えてドツボに嵌りました。
ディスカッション
コメント一覧
まだ、コメントがありません