【算法题】YY and Matrix（矩阵变换）

女爷i 2022-09-15 05:37 131阅读 0赞

## YY and Matrix ##

**★题目描述**

YY 有一个大小为  
n∗m  
的矩阵，现在要对矩阵进行q次操作，操作分为如下三种：

0 x y：交换矩阵的x、y两行。

1 x y：交换矩阵的x、y两列。

2 x y：求当前矩阵第x行第y列的元素。

**★输入**  
第一行三个正整数n、m、q，表示矩阵大小和操作次数。

接下来n行，每行m个空格隔开的整数，表示矩阵的元素。

接下来q行，每行三个数op、x、y，表示上述操作中的一种。

对于80%的数据，1 <= n、m、q <= 1000。

对于100%的数据，1 <= n、m <= 1000,1 <= q <= 1000000,矩阵元素大小在int范围内且非负。

**★输出**  
对于操作2，输出一个整数，表示对应的元素。

**★输入样例**  
2 2 6  
1 2  
3 4  
0 1 2  
1 1 2  
2 1 1  
2 1 2  
2 2 1  
2 2 2  
**★输出样例**  
4  
3  
2  
1

## 1、额外数组记录行列 ##

#include<iostream>
    using namespace std;
    
    //int mat[1001][1001];
    //int col[1001];
    //int row[1001];
    
    int main()
    {
        
    	int n,m,q,op,a,b;
    	scanf("%d %d %d",&n,&m,&q);
    	int mat[n+1][m+1];
    	int col[m+1];
    	int row[n+1];
    	for(int i=1; i<=n; i++) {
        
    		row[i] = i;
    		for(int j=1; j<=m; j++) {
         //警醒！m写成n，直接0分!!! 
    			col[j] = j;
    			scanf("%d",&mat[i][j]);
    		}
    	}
    	while(q--) {
        
    		scanf("%d %d %d",&op,&a,&b);
    		if(op==0) {
        
    			swap(row[a],row[b]);
    		} else if(op==1) {
        
    			swap(col[a],col[b]);
    		} else {
        
    			printf("%d\n",mat[row[a]][col[b]]);
    		}
    	}
    	return 0;
    }

## 2、直接暴力 ##

#include <iostream>
    using namespace std;
    const int maxn=1e7+10;
    typedef long long ll;
    int mat[1002][1002];
    int main()
    {
        
    	int n,m,q,op,a,b;
    	scanf("%d %d %d",&n,&m,&q);
    	
    	for(int i=1; i<=n; i++) {
        
    		for(int j=1; j<=m; j++) {
        
    			scanf("%d",&mat[i][j]);
    		}
    	}
    	while(q--) {
        
    		scanf("%d %d %d",&op,&a,&b);
    		if(op==0) {
        
    			for(int i=1; i<=m; i++) {
        
    				int t = mat[a][i];
    				mat[a][i] = mat[b][i];
    				mat[b][i] = t;
    			}
    		} else if(op==1) {
        
    			for(int i=1; i<=n; i++) {
        
    				int t = mat[i][a];
    				mat[i][a] = mat[i][b];
    				mat[i][b] = t;
    			}
    		} else {
        
    			printf("%d\n",mat[a][b]);
    		}
    	}
    	return 0;
    }

两种方法性能差异  
![在这里插入图片描述][f9d4fa93a35a486281c6830c7bc1d29f.png]

[f9d4fa93a35a486281c6830c7bc1d29f.png]: /images/20220828/61d2d12c79ee47a298679334b861a842.png