一、首先将每个数的位置坐标记录在表中方便查阅

注意题目给的有问题,实际矩阵应为:

1 2 3

4 5 6

7 8 9

0

即:0是在第二列的位置,而不是题目给的第一列

二、通过模拟一个数生成的过程来检验一个数是否合法

例子:

如果要生成58,则遍历字符串,5的行列值是[2,2],8的行列值是[3,2],那么符合8的行列值都分别大于等于2的行列值,即满足“不动、向下或向右移动”的条件,可以生成;

而如果要生成57,则遍历字符串,5的行列值是[2,2],7的行列值是[3,1],那么7的列值1<5的列值2,即不满足“向右移动”,则不可生成。

三、如何寻找最近的符合条件的值,注意剪枝

由于测试用例中有极大的数,即使是long long类型也不足以存放,因此使用字符串来进行操作

而注意到,如果一个数不符合条件,那么仅将其减1是复杂度过大而且不必要的做法,需要的是从不符合条件的位置进行更改

或者换个说法,记忆化搜索

例如,74218 这样的数,从第二位数"5"开始就已经可以判断整个数不符合条件,因此仅将其减1是远远不够的,起码也要将这一位及之后的全部更改,改为73000才有可能搜索到合适的数;以此类推,再搜索到72000、71000,直到70000才能找到合适的数;

而对于90000这样的数,第二位数"0"已经不符合,这种情况下,应从89999开始搜索。

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

// 每个数分别在第几行第几列
vector<pair<int, int>> table = {
    {4, 2},
    {1, 1}, {1, 2}, {1, 3},
    {2, 1}, {2, 2}, {2, 3},
    {3, 1}, {3, 2}, {3, 3}
};

// 检验一个数是否合法,不合法的话返回不合法的位置
pair<bool, int> check(string str) {
    // str当前位数字在表中的行列值
    int currRow = table[str[0] - '0'].first;
    int currCol = table[str[0] - '0'].second;
    for (int i = 1; i < str.size(); i++) {
        // 下一位数字在表中的行列值
        int newRow = table[str[i] - '0'].first;
        int newCol = table[str[i] - '0'].second;
        // 更新行列值
        if (newRow >= currRow && newCol >= currCol) {
            currRow = newRow;
            currCol = newCol;
        } else {
            return {false, i};
        }
    }
    return {true, 0};
}

int main() {
    int T;
    while (cin >> T) {
        string str;
        while (cin >> str) {
            while (true) { // 必定能找到符合的数,因此while true
                const auto& [flag, pos] = check(str);
                if (flag) {
                    cout << str << endl;
                    break; // 找到后跳出
                } else {
                    if (str[pos] == '0') { // 当前位为0,如300,则下一个搜索的数应当是299
                        str[pos - 1]--;
                        for (int i = pos; i < str.size(); i++) {
                            str[i] = '9';
                        }
                    } else { // 当前位不是0,如94666,则下一个搜索的数应当是93999
                        str[pos]--;
                        for (int i = pos + 1; i < str.size(); i++) {
                            str[i] = '9';
                        }
                    }
                }
            }
        }
    }
    return 0;
}

时间复杂度:主要的时间复杂度在于check函数中的for循环,该循环的时间复杂度为O(n),其中n为数的位数。在主函数中,每次调用check函数的时间复杂度也为O(n)。因此,总的时间复杂度为O(n^2)。

空间复杂度:O(n),其中n为数的位数,用于存储输入的数。