题解 | #棋盘#

方法：逆向思维+BFS/DFS

逆向思维：从终点逆向出发。由于正向的a_next >=a_now+b_now，则逆向表示a_now>=a_next+b_next，所以从重点出发进行搜索，每次找到一个满足条件的点就需要更新答案。

搜索（以BFS为例）：经典bfs，queue

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;
const int MOD = 1e5 + 7;

int n, m;
int a[MAXN][MAXN];
int b[MAXN][MAXN];
int next_x[4] = {-1, 0, 1, 0};
int next_y[4] = {0, 1, 0, -1};

int bfs(int x, int y) {
    int ret = 1;
    queue<pair<int, int> >q;
    while (!q.empty())q.pop(); //make it clear

    q.push(pair<int, int>(x, y)); //the first point
    while (!q.empty()) {
        pair<int, int>now = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int midx = now.first + next_x[i];
            int midy = now.second + next_y[i];
            if (midx < 1 || midx > n || midy < 1 || midy > m)continue;
            if (a[now.first][now.second] >= a[midx][midy] + b[midx][midy] ) {
//                cout<<"in"<<endl;
                ret = (ret+1)%MOD;
                q.push(pair<int, int>(midx, midy));
            }
//            printf("%d %d %d\n",midx,midy,ret);
        }
    }
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &b[i][j]);
    int _;
    scanf("%d", &_);
    while (_--) {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", bfs(x, y));
    }
}
// 64 位输出请用 printf("%lld")