题目的主要信息：

• 对于最大为$9\ast 99*9$的二维数组检查以下操作是否可能实现，可以实现输出0，不能实现输出-1：
  • 建立一个$mm$行$nn$列的二维数组，不可以超过最大限制
  • 输入$x_{1}x\_1$、$y_{1}y\_1$、$x_{2}x\_2$、$y_{2}y\_2$，交换坐标在$(x_1,y_1)(x\_1,y\_1)$和坐标在$(x_2,y_2)(x\_2,y\_2)$上的两个数
  • 输入$xx$，在第$xx$行上方添加一行，下标0开始，添加后不能超过9
  • 输入$yy$，在第$yy$列左边添加一列，下标0开始，添加后不能超过9
  • 查找坐标为$(x,y)(x,y)$的单元格的元素
• 上述操作除了建表，其余都视作单独操作，不会相互影响
• 进阶要求：时间复杂度$O(1)O(1)$，空间复杂度$O(1)O(1)$

方法一：直接判断

具体做法：

直接输入上述的数据，然后分别判断：

• 对于建表，要判断行列是否大于9
• 对于交换，要查看两个人坐标是否都在刚刚输入的行列范围内
• 对于插入行与插入列，要判断输入是否在刚刚的行列范围内，还要判断添加一行或者一列后是否会超过9
• 对于查找，也是查看输入的坐标是否在行列范围内，与插入无关，是插入前的行列

#include<iostream>
using namespace std;

int main(){
    int m, n;
    while(cin >> m >> n){ //输入矩阵的行与列
        if(m > 9 || n > 9) //行列数小于等于9
            cout << -1 << endl;
        else
            cout << 0 << endl;
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2; //输入要交换位置的两个坐标
        if(x1 >= 0 && x1 < m && y1 >= 0 && y1 < n && x2 >= 0 && x2 < m && y2 >= 0 && y2 < n) //坐标在数组范围内
            cout << 0 << endl;
        else
            cout << -1 << endl;
        int x;
        cin >> x; //输入插入的行
        if(x >= 0 && x < m && m + 1 <= 9) //插入位置在数组范围内，且插入后不会超过9
            cout << 0 << endl;
        else
            cout << -1 << endl;
        int y;
        cin >> y; //输入插入的列
        if(y >= 0 && y < n && n + 1 <= 9) //插入位置在数组范围内，且插入后不会超过9
            cout << 0 << endl;
        else
            cout << -1 << endl;
        cin >> x >> y; //输入要查找的位置
        if(x >= 0 && x < m && y >= 0 && y < n) //在数组范围内
            cout << 0 << endl;
        else
            cout << -1 << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(1)O(1)$，直接判断，无循环
• 空间复杂度：$O(1)O(1)$，无额外空间

方法二：类

具体做法：

也可以写一个matrix的类，将这样一个二维数组封装起来，无论是初始化建表，还是交换、插入、查找都作为这个类的成员函数，成员函数中的内容就是上述方法一各自的判断，根据输入调用成员函数判断输出即可。

#include<iostream>
#include<vector>
using namespace std;

class matrix{
private:
    int m, n; //二维数组的行列
    vector<vector<int>> arr; //二维数组的元素
    
public:
    int init(int m, int n){ //输入m和n，初始化m*n大小的表格。
        if(m > 9 || n > 9)  //行列数小于等于9
            return -1;
        this->m = m;
        this->n = n;    
        arr.resize(m);
        for(int i = 0; i < m; i++)
            arr[i].resize(n);
        return 0;
    }
    
    int swap_two(int x1, int y1, int x2, int y2){
        if(x1 >= 0 && x1 < m && y1 >= 0 && y1 < n && x2 >= 0 && x2 < m && y2 >= 0 && y2 < n){ //坐标在数组范围内
            swap(arr[x1][y1], arr[x2][y2]);
            return 0;
        }
        return -1;
    }
    
    int insert_row(int x){ //输入x，在第x行左边添加一行
        if(x < 0 || x > m - 1 || m + 1 > 9)  //插入位置在数组范围内，且插入后不会超过9
            return -1;
        return 0;
    }
    
    int insert_col(int y){ //输入y，在第y行上方添加一列
        if(y < 0 || y > n - 1 || n + 1 > 9) //插入位置在数组范围内，且插入后不会超过9
            return -1;
        return 0;
    }
    
    int find(int x, int y){ //查找x，y
        if(x >= 0 && x < m && y >= 0 && y < n)
            return 0;
        return -1;
    }
};

int main(){
    matrix mat;
    int m, n, x1, y1, x2, y2, x, y, find_x, find_y;
    while(cin >> m >> n >> x1 >> y1 >> x2 >> y2 >> x >> y >> find_x >> find_y){
        cout << mat.init(m, n) << endl;
        cout << mat.swap_two(x1, y1, x2, y2) << endl;
        cout << mat.insert_row(x) << endl;
        cout << mat.insert_col(y) << endl;
        cout << mat.find(find_x, find_y) << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(1)O(1)$，无循环，直接判断暑促
• 空间复杂度：$O(nm)O(nm)$，初始化了一个$m\ast nm*n$的矩阵