[AOJ] No. 0320 品質管理
問題
方針
コースターの画像のピクセルの添え字は、\( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません