[AOJ] No. 0320 品質管理

2019年12月29日2020年12月18日

問題

方針

コースターの画像のピクセルの添え字は、\( i \) 行 \( j \) 列を表していて、\( 0 \leq i \leq N – 1 \wedge 0 \leq j \leq N – 1 \) として \( 0 \) オリジンとします。ここで、左上のマス \( (r, c) \ ( 0 \leq r \leq \dfrac{N}{2} – 1 \wedge 0 \leq c \leq \dfrac{N}{2} – 1) \) とします。対称な画像は、

\[ (r, c) , (r, \dfrac{N}{2} – c – 1), (\dfrac{N}{2} – r – 1, c), (\dfrac{N}{2} – r – 1, \dfrac{N}{2} – c – 1)\]

の \( 4 \) マスの値が等しくなければなりません。したがって、各マスが等しくないものの集合を管理すれば良いです。各マスの代表値を \( (N – 1)r + c \) として管理します。これは、\( N \times N \) マスに \( 1 \) から \( N^2 \) まで番号を振っていることに対応します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int p[1000][1000]{};
int N;

bool check(int i, int j) {
    if (i >= N / 2) i = N - i - 1;
    if (j >= N / 2) j = N - j - 1;
    if (p[i][j] != p[N - i - 1][j]) return false;
    if (p[i][j] != p[i][N - j - 1]) return false;
    if (p[i][j] != p[N - i - 1][N - j - 1]) return false;
    return true;
}

int to_index(int r, int c) {
    if (r >= N / 2) r = N - r - 1;
    if (c >= N / 2) c = N - c - 1;
    return (N - 1) * r + c;
}

int main() {
    int C;
    cin >> C >> N;
    int D[C - 1];
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < N; j++) {
            p[i][j] = s[j] - '0';
        }
    }
    
    vector<pair<int, int>> q[C - 1];
    for (int i = 0; i < C - 1; i++) {
        cin >> D[i];
        for (int j = 0; j < D[i]; j++) {
            int r, c;
            cin >> r >> c;
            r--;
            c--;
            q[i].push_back(make_pair(r, c));
        }
    }
    int ans = 0;
    int c[N][N]{};
    set<int> s;
    for (int i = 0; i < N / 2; i++) {
        for (int j = 0; j < N / 2; j++) {
            if (!check(i, j)) s.insert(to_index(i, j));
        }
    }
    if (s.size() == 0) ans = 1;

    for (int i = 0; i < C - 1; i++) {
        for (int j = 0; j < D[i]; j++) {
            int r = q[i][j].first;
            int c = q[i][j].second;
            (p[r][c] == 1) ? p[r][c] = 0 : p[r][c] = 1;
            if (!check(r, c)) {
                s.insert(to_index(r, c));
            } else {
                if (s.count(to_index(r, c)) == 1) {
                    s.erase(to_index(r, c));
                }
            }
        }
        if (s.size() == 0) ans++;
    }
    cout << ans << "\n";
    return 0;
}