题解 | #二维数组操作#

二维数组操作

http://www.nowcoder.com/practice/2f8c17bec47e416897ce4b9aa560b7f4

题意

给定数据表，问给定四个操作：交换坐标，添加行，添加列，查询行。的请求是否合法

限制：

所有请求坐标在数据表坐标范围内，且不实际操作（添加行和列并不影响数据表）
增加行和列时，增加后的行列不能超过9x9

方法

实现

因为需要反复比较坐标是否合法

所以直接实现两个范围比较函数validx和validy验证传入的x和y是否合法

对于插入再额外判断和9的大小关系

代码

#include<bits/stdc++.h>
using namespace std;
int m,n;
bool validx(int v){ // 行有效范围
    return v>=0 && v<m;
}
bool validy(int v){ // 列有效范围
    return v>=0 && v<n;
}
int main(){
    while(~scanf("%d %d",&m,&n)){
        printf("0\n");
        int x0,y0,x1,y1;
        scanf("%d %d %d %d",&x0,&y0,&x1,&y1);
        if( validx(x0) && validx(x1) && validy(y0) && validy(y1) ){
            printf("0\n");
        }else{
            printf("-1\n");
        }
        scanf("%d",&x0);
        if(validx(x0) && m < 9){ // 不能超过9
            printf("0\n");
        }else{
            printf("-1\n");
        }
        scanf("%d",&y0);
        if(validy(y0) && n < 9){ // 不能超过9
            printf("0\n");
        }else{
            printf("-1\n");
        }
        scanf("%d %d",&x0,&y0);
        if(validx(x0) && validy(y0)){
            printf("0\n");
        }else{
            printf("-1\n");
        }
    };
    return 0;
}

复杂度分析

时间复杂度: 每个询问都是常数代价操作，所以时间复杂度为 $O (1)$

空间复杂度: 只有常数个变量，所以空间复杂度为 $O (1)$

记录所有有效点

既然m和n不大, 我们可以先计算所有有效点

对于题目样例 4 9 为例子

-	0	1	2	3
0	(0,0)	(1,0)	(2,0)	(3,0)
1	(0,1)	(1,1)	(2,1)	(3,1)
2	(0,2)	(1,2)	(2,2)	(3,2)
3	(0,3)	(1,3)	(2,3)	(3,3)
4	(0,4)	(1,4)	(2,4)	(3,4)
5	(0,5)	(1,5)	(2,5)	(3,5)
6	(0,6)	(1,6)	(2,6)	(3,6)
7	(0,7)	(1,7)	(2,7)	(3,7)
8	(0,8)	(1,8)	(2,8)	(3,8)

全部都会被记入

对于交换的点和查询的点，直接查询是否在上面表中即可

对于插入行和列，因为行和列始终是从0开始，所以查询(行,0)是否存在，和(0,列)是否存在

代码

#include<bits/stdc++.h>
using namespace std;
int m,n;

int main(){
    while(~scanf("%d %d",&m,&n)){
        printf("0\n");
        set<pair<int,int> > s;
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                s.insert({i,j}); // 所有有效点
            }
        }
        int x0,y0,x1,y1;
        scanf("%d %d %d %d",&x0,&y0,&x1,&y1);
        if( s.count({x0,y0}) && s.count({x1,y1}) ){ // 直接检查点
            printf("0\n");
        }else{
            printf("-1\n");
        }
        scanf("%d",&x0);
        if(s.count({x0,0}) && m < 9){ // 另一个坐标为0
            printf("0\n");
        }else{
            printf("-1\n");
        }
        scanf("%d",&y0);
        if(s.count({0,y0}) && n < 9){ // 另一个坐标为0
            printf("0\n");
        }else{
            printf("-1\n");
        }
        scanf("%d %d",&x0,&y0);
        if(s.count({x0,y0})){ // 直接检查点
            printf("0\n");
        }else{
            printf("-1\n");
        }
    };
    return 0;
}