BestCoder Round #81 (Div.2) 1002 Matrix：陣列模擬指針實現行列交換

題目大意

給定一個矩陣，支援三種操作：交換兩行、交換兩列、查詢某個位置的值。由於矩陣尺寸與操作次數均可能較大，若每次交換都真正移動數據，時間複雜度會過高。核心觀察是：無論如何交換行或列，原本屬於同一行的元素始終在同一行，同一列的元素始終在同一列。因此只需維護「當前第 i 行對應原始矩陣的哪一行」以及「當前第 j 列對應原始矩陣的哪一列」的映射關係即可。

解題思路：陣列模擬指針指向

• 使用陣列 row[i] 記錄當前第 i 行實際對應原始矩陣的行號；同理 col[j] 記錄列映射。
• 初始化時 row[i] = i, col[j] = j。
• 交換行操作：只需交換 row[x] 與 row[y]，複雜度 O(1)。
• 交換列操作：同理交換 col[x] 與 col[y]。
• 查詢操作：輸出 a[row[x]][col[y]] 即可。

這種「間接定址」技巧將原本 O(N) 的行列交換降為 O(1)，總複雜度為 O(N^2 + Q)，極大提升效率。

參考代碼 (C++)

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1009;
int mat[MAXN][MAXN];
int row[MAXN], col[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, q;
    while (cin >> n >> m >> q) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                cin >> mat[i][j];
        
        for (int i = 1; i <= n; ++i) row[i] = i;
        for (int j = 1; j <= m; ++j) col[j] = j;
        
        char op;
        int x, y;
        while (q--) {
            cin >> op >> x >> y;
            if (op == 'r') swap(row[x], row[y]);
            else if (op == 'c') swap(col[x], col[y]);
            else cout << mat[row[x]][col[y]] << '\n';
        }
    }
    return 0;
}

核心要點總結

1. 數據與索引分離：不移動實際數據，只維護索引映射。
2. 適用場景：頻繁整行/整列交換、整體平移、循環移位等操作。
3. 擴展性：同理可處理二維陣列的行列翻轉、子矩陣提取等變體問題。