题解 | #Numeric Keypad# 模拟搜索过程

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

注意题目给的有问题，实际矩阵应为：

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为数的位数，用于存储输入的数。