Codeforces Round #367 (Div. 2) E. Working routine
問題
N*M のグリッドが与えられる。各クエリで 「(a, b), (c, d) を左上の頂点とする高さ h, 幅 w の領域を交換する」ということをする(ただし, 交換する長方形は辺やセルを共有しない)。
全てのクエリを処理した後の最終的なグリッドの状態を求めよ。
解法
リストの考え方を応用すると解けます。
各ノードに「左隣, 右隣, 上隣, 下隣」のノードを覚えてもらうと, 領域内のほとんどのセルは隣接するセルが変化せず, 領域の周りのセルだけ隣接関係が変わっていることに注意すると, 各クエリは O(N+M) で処理できます。下の図を見ると多少イメージがわくと思います。
隣接関係の更新の仕方(というか順番)は工夫しないと簡単にバグるので注意です。
const int MAX = 1010; struct Node { Node() {init();} Node(int r, int c) : r(r), c(c) {init();} void init() { right = NULL; left = NULL; top = NULL; bottom = NULL; } int r; int c; Node* right; Node* left; Node* top; Node* bottom; }; Node* nodes[MAX][MAX]; int board[MAX][MAX]; int N, M, Q; // node1 <-> node2, node3 <-> node4 void changeNode1(Node* node1, Node* node2, Node* node3, Node* node4) { node1->right = node4; node3->right = node2; node2->left = node3; node4->left = node1; } // node1, node3 // node2, node4 void changeNode2(Node* node1, Node* node2, Node* node3, Node* node4) { node1->bottom = node4; node3->bottom = node2; node2->top = node3; node4->top = node1; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M >> Q; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) cin >> board[i][j]; for (int i = 0; i <= N+2; i++) for (int j = 0; j <= M+2; j++) nodes[i][j] = new Node(i, j); for (int i = 0; i <= N+1; i++) { for (int j = 0; j <= M+1; j++) { if (i) nodes[i][j]->top = nodes[i-1][j]; if (j) nodes[i][j]->left = nodes[i][j-1]; nodes[i][j]->right = nodes[i][j+1]; nodes[i][j]->bottom = nodes[i+1][j]; } } while (Q--) { int a, b, c, d, h, w; cin >> a >> b >> c >> d >> h >> w; Node* root1 = nodes[a][0]; Node* root2 = nodes[c][0]; for (int i = 0; i < b; i++) root1 = root1->right; for (int i = 0; i < d; i++) root2 = root2->right; // 上辺, 右辺 { Node* now1 = root1; Node* now2 = root2; for (int i = 0; i < w; i++) { changeNode2(now1->top, now1, now2->top, now2); now1 = now1->right; now2 = now2->right; } for (int i = 0; i < h; i++) { changeNode1(now1->left, now1, now2->left, now2); now1 = now1->bottom; now2 = now2->bottom; } } // 左辺, 下辺 { Node* now1 = root1; Node* now2 = root2; for (int i = 0; i < h; i++) { changeNode1(now1->left, now1, now2->left, now2); now1 = now1->bottom; now2 = now2->bottom; } for (int i = 0; i < w; i++) { changeNode2(now1->top, now1, now2->top, now2); now1 = now1->right; now2 = now2->right; } } } for (int i = 1; i <= N; i++) { Node* root = nodes[i][0]; for (int j = 0; j < M; j++) { root = root->right; int r = root->r, c = root->c; r--; c--; cout << board[r][c] ; if (j < M-1) cout << " "; } cout << endl; } return 0; }