e974 - 座位安排 (Seats)
題目描述
題目給定一個矩陣的維度 (a, b) 和一個旋轉次數 c。矩陣中的元素初始值為 1 到 a * b 的連續整數，按照列優先的順序填入。每次旋轉，矩陣的最右邊一列會移動到最左邊，或者最下面一行會移動到最上面。要求輸出旋轉 c 次後的矩陣。
解題思路
這題的核心是模擬矩陣旋轉的過程。根據旋轉次數 c 的奇偶性，決定每次旋轉是將最右邊一列移動到最左邊，還是將最下面一行移動到最上面。
- 如果 c 是奇數，則執行列旋轉：將最右邊一列的元素儲存到一個臨時陣列，然後將其他列的元素向右移動一位，最後將臨時陣列的元素填入最左邊一列。
- 如果 c 是偶數，則執行行旋轉：將最下面一行的元素儲存到一個臨時陣列，然後將其他行的元素向下移動一位，最後將臨時陣列的元素填入最上面一行。 重複以上步驟 c 次，即可得到旋轉後的矩陣。
複雜度分析
- 時間複雜度: O(a * b * c)，其中 a 和 b 是矩陣的維度，c 是旋轉次數。因為每次旋轉都需要遍歷整個矩陣。
- 空間複雜度: O(max(a, b))，因為需要使用臨時陣列來儲存旋轉時的元素。臨時陣列的大小取決於矩陣的行數和列數的最大值。
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int a,b,c,w=0;
cin >> a >> b >> c;
int sit[a][b],n=1,right[a],back[b];
for(int i=0;i<a;i++)
for(int j=0;j<b;j++)
sit[i][j]=n++;
while(++w!=c){
if(w&1){
for(int i=0;i<a;i++)
right[i]=sit[i][b-1];
for(int j=b-2;j>=0;j--)
for(int i=0;i<a;i++)
sit[i][j+1]=sit[i][j];
for(int i=0;i<a;i++)
sit[i][0]=right[i];
}
else{
for(int j=0;j<b;j++)
back[j]=sit[a-1][j];
for(int i=a-2;i>=0;i--)
for(int j=0;j<b;j++)
sit[i+1][j]=sit[i][j];
for(int j=0;j<b;j++)
sit[0][j]=back[j];
}
}
for(int i=0;i<a;i++){
for(int j=0;j<b;j++)
cout << sit[i][j] << " ";
cout << "\n";
}
}