题意

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

限制：

  1. 所有请求坐标在数据表坐标范围内，且不实际操作（添加行和列并不影响数据表）
  2. 增加行和列时，增加后的行列不能超过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)

空间复杂度: 只有常数个变量，所以空间复杂度为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;
}

复杂度分析

时间复杂度: 因为计算了所有有效点O(nm)O(nm)

空间复杂度: 储存了所有有效点,O(mn)O(mn)