题解 | #棋盘#

棋盘

https://www.nowcoder.com/practice/aa1710fef87a43e390fde7f236452df3

#include <iostream> 
#include <vector> 
#include <algorithm> 

const long mod = 100007;

using namespace std;

vector<vector<long long>> mem;

long long cnt = 0;
long long mem_track(vector<vector<int>>& a,vector<vector<int>>& b,int endx,int endy,vector<vector<bool>>& vis){
    
    if(vis[endx][endy]) return mem[endx][endy];
    
    vis[endx][endy] = true;
    mem[endx][endy] = 1;
    if(endx - 1 >= 0 && a[endx-1][endy] + b[endx-1][endy] <= a[endx][endy]) {mem[endx][endy] += mem_track(a,b,endx-1,endy,vis); mem[endx][endy] %= mod;}
    if(endx + 1 < a.size() && a[endx+1][endy] + b[endx+1][endy] <= a[endx][endy]) {mem[endx][endy] += mem_track(a,b,endx+1,endy,vis); mem[endx][endy] %= mod;}
    if(endy - 1 >= 0 && a[endx][endy-1] + b[endx][endy-1] <= a[endx][endy]) {mem[endx][endy] += mem_track(a,b,endx,endy-1,vis); mem[endx][endy] %= mod;}
    if(endy + 1 < a[0].size() && a[endx][endy+1] + b[endx][endy+1] <= a[endx][endy]) {mem[endx][endy] += mem_track(a,b,endx,endy+1,vis); mem[endx][endy] %= mod;}
    
    return mem[endx][endy];
}


int main(){
    int n = 0, m = 0;
    cin >> n >> m;
    vector<vector<int>> a(n,vector<int>(m));
    vector<vector<int>> b(n,vector<int>(m));
    
    mem.resize(n,vector<long long>(m));
    
    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 q = 0;
    cin >> q;
    vector<vector<bool>> vis(n,vector<bool>(m,false));
    
    while(q--){
        int x ,y;
        cin >> x >> y;
        cout << mem_track(a,b,x-1,y-1,vis) << endl;
    }
    return 0;
}

全部评论

相关推荐

沉淀一会:1.同学你面试评价不错,概率很大,请耐心等待; 2.你的排名比较靠前,不要担心,耐心等待; 3.问题不大,正在审批,不要着急签其他公司,等等我们! 4.预计9月中下旬,安心过节; 5.下周会有结果,请耐心等待下; 6.可能国庆节前后,一有结果我马上通知你; 7.预计10月中旬,再坚持一下; 8.正在走流程,就这两天了; 9.同学,结果我也不知道,你如果查到了也告诉我一声; 10.同学你出线不明朗,建议签其他公司保底! 11.同学你找了哪些公司,我也在找工作。
点赞 评论 收藏
分享
头像
10-22 19:18
上海大学 后端
jopajhhdjwnqk:水印都叠杀人书了
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务