各大网站收录提交入口网站建设基础与网页设计

题目描述

小明班上是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;
}

解题思路

1. 初始化行和列的映射数组：我们使用两个数组p和q来分别记录行和列的当前映射关系。初始时，p[i] = i表示第i行当前还是原来的第i行，q[j] = j表示第j列当前还是原来的第j列。

2. 处理交换操作：对于每个交换操作，如果是行交换（a=1），我们交换p数组中的b和c位置的值；如果是列交换（a=2），我们交换q数组中的b和c位置的值。

3. 查询最终座位号：根据处理后的p和q数组，找到第x行和第y列对应的原始行和列。原始座位号的计算公式为  (原始行-1)*m+原始列 ，其中m是列数。

4. (直接用二维数组模拟会超时)