Submission #1224411

#TimeUsernameProblemLanguageResultExecution timeMemory
1224411AishaGame (eJOI20_game)C++20
0 / 100
0 ms328 KiB
#include "bits/stdc++.h"

using namespace std;

#define int long long

signed main() {
    int n, m;
    cin >> n >> m;

    vector <vector <int>> g(n * m + 2 * m);
    for (int i = 0; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            char c;
            cin >> c;
            if (c == '0') {
               // cout << (i - 1) * m + j << ' ' << i * m + j << endl;
                g[max(0ll, (i - 1) * m + j - 1)].push_back(max(0ll, i * m + j - 1));
                g[max(0ll, i * m + j - 1)].push_back(max(0ll, (i - 1) * m + j - 1));
            }
        }
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= m; j ++) {
            char c;
            cin >> c;
            if (c == '0') {
             //   cout << (i - 1) * m + j << ' ' << (i - 1) * m + j + 1 << endl;
                g[max(0ll, (i - 1) * m + j - 1)].push_back((i - 1) * m + j);
                g[(i - 1) * m + j].push_back(max(0ll, (i - 1) * m + j - 1));
            }
        }
    }

    vector <int> comp, vis((n + 1) * (m + 1)), c;

    auto dfs = [&](auto&& dfs, int i, int j) -> void {
        if (i == 0 || j == 0 || i > n || j > m) return;
        if (vis[(i - 1) * m + j - 1]) return;
        vis[(i - 1) * m + j - 1] = 1; int k = (i - 1) * m + j - 1;
        c.push_back(k);
        for (int x : g[k]) {
            int i1 = x / m + 1, j1 = x % m;
           // cout << x << endl;
          //  cout << i1 << ' ' << j1 << endl;
            dfs(dfs, i1, j1);
        }
    };

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            if (vis[(i - 1) * m + j - 1]) continue;
            dfs(dfs, i, j);
            if ((int)c.size() == 1) {
                c.clear();
                continue;
            }
           // cout << c.size() << endl;
            comp = c;
          //  cout << i << ' ' << j << endl;
            break;
        }
        if (comp.size()) break;
    }

    cout << -(int)comp.size() << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...