点击打开题目
B. Cosmic Tables
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The Free Meteor Association (FMA) has got a problem: as meteors are moving, the Universal Cosmic Descriptive Humorous Program (UCDHP) needs to add a special module that would analyze this movement.
UCDHP stores some secret information about meteors as an n × m table with integers in its cells. The order of meteors in the Universe is changing. That's why the main UCDHP module receives the following queries:
As the main UCDHP module is critical, writing the functional of working with the table has been commissioned to you.
Input
The first line contains three space-separated integers n, m and k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 500000) — the number of table columns and rows and the number of queries, correspondingly.
Next n lines contain m space-separated numbers each — the initial state of the table. Each number p in the table is an integer and satisfies the inequality 0 ≤ p ≤ 106.
Next k lines contain queries in the format "si xi yi", where si is one of the characters "с", "r" or "g", and xi, yi are two integers.
The table rows are considered to be indexed from top to bottom from 1 to n, and the table columns — from left to right from 1 to m.
Output
For each query to obtain a number (si = "g") print the required number. Print the answers to the queries in the order of the queries in the input.
Examples
input
3 3 5
1 2 3
4 5 6
7 8 9
g 3 2
r 3 2
c 2 3
g 2 2
g 3 2
output
8
9
6
input
2 3 3
1 2 4
3 1 5
c 2 1
r 1 2
g 1 3
output
5
Note
Let's see how the table changes in the second test case.
After the first operation is fulfilled, the table looks like that:
2 1 4
1 3 5
After the second operation is fulfilled, the table looks like that:
1 3 5
2 1 4
So the answer to the third query (the number located in the first row and in the third column) will be 5.
以前做过一个,题意是把给定的行(列)加到另一行(列)上,用的是并查集,感觉那个思路很好。这道题要求是交换,就不能用并查集了。
刚开始绕弯很多,主要是没搞懂数组的值表示的含义。
下面代码,r [ ] 、c [ ] 数组分别表示现在的行和列表示原有的哪一行(列)。(这点一定要清楚,要不写代码的时候就搞晕了)
那么明白了含义后,进行交换操作就简单多了,(媳妇儿说坑坑坑),把当前行(列)表示的真正数值直接交换就行了。
代码如下:
#include <cstdio>
#include <algorithm>
using namespace std;
int h,w,k;
int mapp[1011][1011];
int c[1011],r[1011]; //c为列,r为行: 表示第几行(列)的数表示原来的第几行(列)
void init()
{
int l;
l = max (w,h);
for (int i = 1 ; i <= l ; i++)
c[i] = r[i] = i;
}
int main()
{
char op[4];
int x,y;
while (~scanf ("%d %d %d",&h,&w,&k))
{
init(); //初始化
for (int i = 1 ; i <= h ; i++)
for (int j = 1 ; j <= w ; j++)
scanf ("%d",&mapp[i][j]);
for (int i = 1 ; i <= k ; i++)
{
scanf ("%s %d %d",op,&x,&y);
if (op[0] == 'r')
swap (r[x] , r[y]);
else if (op[0] == 'c')
swap (c[x] , c[y]);
else
printf ("%d\n",mapp[r[x]][c[y]]);
}
}
return 0;
}