Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

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

Codeforces こどふぉ competitive programming c++

見た目に騙されました・・・。こどふぉギャグでした・・・。

問題

https://codeforces.com/contest/1421/problem/B

問題概要

n\times nのグリッドがあり、(1,1)と(n,n)以外のすべてのマスには0または1の値が与えられている。

隣接するセル（上下左右）のうち、0のセルのみ、または1のセルのみを辿って、(1,1)から(n,n)`まで移動するという作業を考える。

あなたの目的は最大2つまでのセルの数字を反転させることで、上記の作業を達成不可能にすることである。反転させるセルの座標を最大2つまで示せ。

考察

(1,1)の周囲を0 0、(n,n)の周囲を1 1としてしまえば（もちろん1 1と0 0でもよい）、途中の状態がどうであれ作業の達成は不可能です。つまりこういう状態です。

S0__
0___
___1
__1F

そして、初期状態がいかなる場合でも、たかだか2回の反転でそのような状態を作ることが可能です。

列挙すると

  • Sが0 0のとき
    • Fが0 0のとき
      • Fを1 1とすればよいです（2回）
    • Fが0 1のとき
      • Fを1 1とすればよいです（1回）
    • Fが1 1のとき
      • 何もしなくてよいです（0回）
  • Sが0 1のとき
    • Fが0 0のとき
      • Sを1 1とすればよいです（1回）
    • Fが0 1のとき
      • Sを0 0、Fを1 1とすればよいです（2回）
    • Fが1 1のとき
      • Sを0 0とすればよいです（1回）
  • Sが1 1のとき
    • Fが0 0のとき
      • 何もしなくてよいです（0回）
    • Fが0 1のとき
      • Fを0 0とすればよいです（1回）
    • Fが1 1のとき
      • Fを0 0とすればよいです（2回）

となります。

#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, (n))
#define sz(v) (int)v.size()
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<string> s(n);
        REP(i, n) cin >> s[i];

        vector<pair<int, int>> ans;
        bool s_diff = s[0][1] != s[1][0];
        bool f_diff = s[n - 1][n - 2] != s[n - 2][n - 1];
        if (s_diff == false and f_diff == false) {
            if (s[0][1] == s[n - 1][n - 2]) {
                ans.emplace_back(1, 2);
                ans.emplace_back(2, 1);
            }
        } else if (s_diff == false) {
            if (s[0][1] == s[n - 1][n - 2]) ans.emplace_back(n, n - 1);
            if (s[0][1] == s[n - 2][n - 1]) ans.emplace_back(n - 1, n);
        } else if (f_diff == false) {
            if (s[0][1] == s[n - 1][n - 2]) ans.emplace_back(1, 2);
            if (s[1][0] == s[n - 2][n - 1]) ans.emplace_back(2, 1);
        } else {
            if (s[0][1] == '1') ans.emplace_back(1, 2);
            if (s[1][0] == '1') ans.emplace_back(2, 1);
            if (s[n - 1][n - 2] == '0') ans.emplace_back(n, n - 1);
            if (s[n - 2][n - 1] == '0') ans.emplace_back(n - 1, n);
        }

        cout << sz(ans) << endl;
        for (auto aa : ans) cout << aa.first << " " << aa.second << endl;
    }
}

感想

私は問題の見た目に騙されて（？）十分な考察をせずにBFSを実装してしまい、いざ答えを判定する段になってから自分の誤りに気づきました・・・。

くれぐれも実装は十分な考察を行う前にはしないようにしましょう。