题解 | #棋盘#

写一个不使用回溯的算法，而是使用排序的代码，时间复杂度是排序的耗时$n\ast m\ast log(n\ast m)n*m*log(n*m)$.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// 自定义一个二维向量的排序规则，按照总和从小到大排序
bool cmp(vector<int>& a, vector<int>& b) {
    return a[0] < b[0];
}

int main() {
    int n, m;
    cin >> n >> m;

    // 定义两个 n*m 的二维向量 a 和 b，每个位置上的值分别为输入的整数
    vector<vector<int>> a(n, vector<int>(m, 0)), b(n, vector<int>(m, 0));

    // 定义一个 n*m 的二维向量 total，每个位置上的值由 a 和 b 对应位置上的数相加得到
    // 第一列表示总和，第二列表示行，第三列表示列
    vector<vector<int>> total(n * m, vector<int>(3, 0));

    // 遍历 a 数组，输入每个位置上的值
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    // 遍历 b 数组，输入每个位置上的值，并计算对应位置上的总和，存入 total 中
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> b[i][j];
            total[i * m + j][0] = b[i][j] + a[i][j];
            total[i * m + j][1] = i;
            total[i * m + j][2] = j;
        }
    }

    // 定义一个 n*m 的二维向量 res，每个位置上的值为 1，表示路径条数
    vector<vector<int>> res(n, vector<int>(m, 1));

    // 按照总和从小到大排序
    sort(total.begin(), total.end(), cmp);

    // 按照排好序的顺序遍历 total，更新 res 数组
    for(int i = 0; i < n * m; i++) {
        int x = total[i][1];
        int y = total[i][2];

        // 如果上方格子的值大于等于当前位置的总和，说明可以从上一步到达当前位置，更新 res 数组
        if(x - 1 >= 0 && a[x-1][y] >= total[i][0]) {
            res[x - 1][y] = (res[x][y] + res[x - 1][y]) % 100007;
        }

        // 同理，更新左侧格子
        if(y - 1 >= 0 && a[x][y - 1] >= total[i][0]) {
            res[x][y - 1] = (res[x][y] + res[x][y - 1]) % 100007;
        }

        // 同理，更新下方格子
        if(x + 1 < n && a[x+1][y] >= total[i][0]) {
            res[x + 1][y] = (res[x][y] + res[x + 1][y]) % 100007;
        }

        // 同理，更新右侧格子
        if(y + 1 < m && a[x][y + 1] >= total[i][0]) {
            res[x][y + 1] = (res[x][y] + res[x][y + 1]) % 100007;
        }
    }

    // 输入询问数量 q
    int q;
    cin >> q;

    // 遍历询问，输出 res 数组对应位置上的值
    int x, y;
    for(int i = 0; i < q; i++) {
        cin >> x >> y;
        cout << res[x - 1][y - 1] << endl;
    }

    return 0;
}