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

2020年12月12日

問題

方針

どのような状態だと '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;
}

感想

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