# 矩陣查詢 > 原文： [https://www.geeksforgeeks.org/queries-in-a-matrix/](https://www.geeksforgeeks.org/queries-in-a-matrix/) 給定大小為 m x n（1 < = m，n < = 1000）的矩陣 M。 最初按行主順序依次填充從 1 到 m x n 的整數。 任務是處理操縱 M 的查詢列表，以使每個查詢都是以下三個之一。 1. **R（x，y）**：交換 M 的第 x 和 y 行，其中 x 和 y 從 1 到 m 變化。 2. **C（x，y）**：交換 M 的第 x 和 y 列，其中 x 和 y 在 1 到 n 之間變化。 3. **P（x，y）**：在第 x 行和第 y 列打印元素，其中 x 從 1 到 m 變化，而 y 從 1 到 n 變化。 請注意，給定矩陣存儲為典型的 2D 數組，索引從 0 開始，但是 x 和 y 的值從 1 開始。 例子： ``` Input : m = 3, n = 3 R(1, 2) P(1, 1) P(2, 1) C(1, 2) P(1, 1) P(2, 1) Output: value at (1, 1) = 4 value at (2, 1) = 1 value at (1, 1) = 5 value at (2, 1) = 2 Explanation: The matrix is {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}} After first R(1, 2) matrix becomes, {{4, 5, 6}, {1, 2, 3}, {7, 8, 9}} After first C(1, 2) matrix becomes, {{5, 4, 6}, {2, 1, 3}, {8, 7, 9}} Input : m = 1234, n = 5678 R(1, 2) P(1, 1) P(2, 1) C(1, 2) P(1, 1) P(2, 1) Output: value at (1, 1) = 5679 value at (2, 1) = 1 value at (1, 1) = 5680 value at (2, 1) = 2 ``` 解決此問題的**簡單解決方案**是手動完成所有查詢，這意味著當我們不得不交換行時，只需交換第 x 行和第 y 行的元素，并且類似地進行列沼澤。 但是這種方法的時間復雜度可能為 q * O（m）或 q *`O(n)`，其中“ q”是查詢數，所需輔助空間為 O（m * n）。 解決此問題的有效方法**幾乎不需要數學觀察。 在這里，我們給出矩陣中的元素按行主要順序從 1 到 mxn 依次填充，因此我們將利用此給定方案并解決此問題。** * 創建一個輔助數組 rows [m]，并將其值從 0 到 m-1 依次填充。 * 創建另一個輔助數組 cols [n]并依次將其值從 0 填充到 n-1。 * 現在，對于查詢“ R（x，y）”，只需將 rows [x-1]的值替換為 rows [y-1]。 * 現在，對于查詢“ C（x，y）”，只需將 cols [x-1]的值與 cols [y-1]交換即可。 * 現在，對于查詢“ P（x，y）”，只需跳過您已經看到的列數，并通過**行[x-1] * n + cols [y-1] +計算（x，y）處的值 1** 。 以下是上述想法的實現。 ## C++ ```cpp // C++ implementation of program #include<bits/stdc++.h> using namespace std; // Fills initial values in rows[] and cols[] void preprocessMatrix(int rows[], int cols[], ?????????????????????int m, int n) { ????// Fill rows with 1 to m-1 ????for (int i=0; i<m; i++) ????????rows[i] = i; ????// Fill columns with 1 to n-1 ????for (int i=0; i<n; i++) ????????cols[i] = i; } // Function to perform queries on matrix // m --> number of rows // n --> number of columns // ch --> type of query // x --> number of row for query // y --> number of column for query void queryMatrix(int rows[], int cols[], int m, ?????????????????int n, char ch, int x, int y) { ????// perform queries ????int tmp; ????switch(ch) ????{ ????case 'R': ????????// swap row x with y ????????swap(rows[x-1], rows[y-1]); ????????break; ????case 'C': ????????// swap coloumn x with y ????????swap(cols[x-1], cols[y-1]); ????????break; ????case 'P': ????????// Print value at (x, y) ????????printf("value at (%d, %d) = %d\n", x, y, ???????????????????rows[x-1]*n + cols[y-1]+1); ????????break; ????} ????return ; } // Driver program to run the case int main() { ????int m = 1234, n = 5678; ????// row[] is array for rows and cols[] ????// is array for coloumns ????int rows[m], cols[n]; ????// Fill initial values in rows[] and cols[] ????preprocessMatrix(rows, cols, m, n); ????queryMatrix(rows, cols, m, n, 'R', 1, 2); ????queryMatrix(rows, cols, m, n, 'P', 1, 1); ????queryMatrix(rows, cols, m, n, 'P', 2, 1); ????queryMatrix(rows, cols, m, n, 'C', 1, 2); ????queryMatrix(rows, cols, m, n, 'P', 1, 1); ????queryMatrix(rows, cols, m, n, 'P', 2, 1); ????return 0; } ```