C++ 记忆化搜索题解 | #棋盘#

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

int MOD = 100007;
vector<vector<int>> A,B;
int n , m;

vector<vector<int>> memo;
vector<vector<bool>> visited;
vector<vector<int>> neis = {{0,1},{1,0},{-1,0},{0,-1}};
int dfs(int i , int j){
    int &res = memo[i][j];
    if(res != -1) return res;
    int ret = 1;
    int cur = A[i][j];
    
    for(int dir = 0 ; dir < 4 ; dir++){
        int next_i = i+neis[dir][0];
        int next_j = j+neis[dir][1];
	    // 使用visited标记 防止左右横跳 或者上下横跳的情况.
        if(next_i >= 0 && next_i < n && next_j >= 0 && next_j < m &&
          (A[next_i][next_j] + B[next_i][next_j]) <= cur && !visited[next_i][next_j]){
            visited[next_i][next_j] = true;
            ret = (ret + dfs(next_i,next_j) ) % MOD;
            visited[next_i][next_j] = false;
        }
    }

    return res = ret;
}

int main() {
    cin >> n >> m;
    A.resize(n,vector<int>(m));
    B.resize(n,vector<int>(m));
    memo.resize(n+1,vector<int>(m+1,-1));
    visited.resize(n,vector<bool>(m,false));

    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            cin >> A[i][j];
        }
    }

    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            cin >> B[i][j];
        }
    }

    int query_n; cin >> query_n;
    vector<std::pair<int,int>> querys(query_n);
    for(int i = 0 ; i < query_n ; i++){
        cin >> querys[i].first >> querys[i].second;
        querys[i].first--;
        querys[i].second--;
    }

    for(auto &it : querys){
        int res = dfs(it.first,it.second);
        std::cout << res << std::endl;
    }
    
}
// 64 位输出请用 printf("%lld")