題目描述
小明班上是n行m列的座位排列，座位按照行列順序編號，如6行7列，那么第1行第1列座位號為1號、第1行第7列為7號、第3行第4列為18號，如此遞推。
現在期中考剛結束要進行全班換座位。班主任剛剛公布了換位指令，指令一共z條且只有以下幾類：
①行對換；
②列對換。
請你根據換位指令找到換位結束后第x行第y列的原座位號。
輸入格式
第一行為三個整數，分別為n、m、z，以空格隔開，整數含義如題所示。
第二至z+1行有三個整數，分別為a、b、c。若a為1，則將bc行對換；若a為2，則將bc列對換。
最后一行有兩個整數，分別為x和y，整數含義如題所示。
輸出格式
輸出1行，輸出第x行第y列的原座位號。
?輸入輸出樣例 1
輸入 #1
5 5 2
1 1 2
2 3 1
1 1
輸出 #1
8
?
說明/提示
對于60%的數據：1≤n,m,z≤1000；
對于100%的數據：1≤n,m≤5000，1≤z≤100000。
參考答案
#include <iostream>
using namespace std;
int main()
{int n,m,z,x,y;int p[5001],q[5001],a,b,c;cin>>n>>m>>z;for(int i=1;i<=n;i++) p[i]=i;for(int i=1;i<=m;i++) q[i]=i;for(int i=1;i<=z;i++){cin>>a>>b>>c;if(a==1)swap(p[b],p[c]);else swap(q[b],q[c]);}cin>>x>>y;int row=p[x];int col=q[y];cout<<(row-1)*m+col;return 0;
}解題思路
-
初始化行和列的映射數組：我們使用兩個數組
p和q來分別記錄行和列的當前映射關系。初始時，p[i] = i表示第i行當前還是原來的第i行，q[j] = j表示第j列當前還是原來的第j列。 -
處理交換操作：對于每個交換操作，如果是行交換（a=1），我們交換
p數組中的b和c位置的值；如果是列交換（a=2），我們交換q數組中的b和c位置的值。 -
查詢最終座位號：根據處理后的
p和q數組，找到第x行和第y列對應的原始行和列。原始座位號的計算公式為? (原始行-1)*m+原始列?，其中m是列數。 -
(直接用二維數組模擬會超時)
)