Hướng dẫn giải của Chọn Đội tuyển HSGQG Huế 2024 - Biến đổi bảng
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Subtask 1: Since there exists a transformation consisting of no more than ~1~ operation, we can easily find the cell that needs to be transformed. Complexity: ~O(m * n)~
Subtask 2 + 3:
Observation: Each cell can be flipped at most ~1~ time because flipping ~2~ times will return to the original color.
From here, we iterate through the cells ~(i, j)~ from top to bottom and from left to right. If the color of the current cell differs from the color of Nam's favorite cell, we perform the transformation operation with the top-left cell as cell ~(i, j)~.
After iterating through all the cells ~(i, j)~, if the current board after transformation matches Nam's favorite board, print YES along with the operations; otherwise, print NO.
Complexity: ~O(4 * m * n)~
#include <bits/stdc++.h> #define BIT(x, k) (((x) >> (k)) & 1) #define on(x, k) ((x) ^ (1ll << (k))) #define pii pair<int, int> #define fi first #define se second #define all(x) x.begin(), x.end() #define ll long long using namespace std; const int N = 102; bool a[N][N], b[N][N]; int m, n; void process() { cin >> m >> n; char c; for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) { cin >> c; a[i][j] = (c == 'B' ? 1 : 0); } for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) { cin >> c; b[i][j] = (c == 'B' ? 1 : 0); } vector<pii> ans; for (int i = 1; i < m; i++) for (int j = 1; j < n; j++) { if (a[i][j] != b[i][j]) { a[i][j] ^= 1; a[i][j + 1] ^= 1; a[i + 1][j] ^= 1; a[i + 1][j + 1] ^= 1; ans.push_back({i, j}); } } for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) if (a[i][j] != b[i][j]) return void (cout << "NO"); cout << "YES\n"; cout << ans.size() << "\n"; for (pii x : ans) cout << x.fi << " " << x.se << "\n"; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define TASK "BOARD" if (fopen(TASK ".INP", "r")) { freopen(TASK ".INP", "r", stdin); freopen(TASK ".OUT", "w", stdout); } process(); cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s"; }
Bình luận