mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #367 (Div. 2) E. Working routine

問題

codeforces.com

N*M のグリッドが与えられる。各クエリで 「(a, b), (c, d) を左上の頂点とする高さ h, 幅 w の領域を交換する」ということをする(ただし, 交換する長方形は辺やセルを共有しない)。
全てのクエリを処理した後の最終的なグリッドの状態を求めよ。

解法

リストの考え方を応用すると解けます。

各ノードに「左隣, 右隣, 上隣, 下隣」のノードを覚えてもらうと, 領域内のほとんどのセルは隣接するセルが変化せず, 領域の周りのセルだけ隣接関係が変わっていることに注意すると, 各クエリは O(N+M) で処理できます。下の図を見ると多少イメージがわくと思います。
f:id:mayokoex:20160917112933j:plain

隣接関係の更新の仕方(というか順番)は工夫しないと簡単にバグるので注意です。

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;
}