题解 P7074 【方格取数（暂无数据）】

isnot_prime · 2020-11-07 20:11:16 · 题解

刚刚考完试，就看没人发题解，就来水一篇

这题一看，我就想到用dfs打

首先从起始位置开始搜，搜到最后位置结束，再用vis记录每一步所加之和，每种走到终点的方案所加之和，在与maxn比较，比maxn大就更新，搜完所有方案就输出最大值了

注意：要判断是否越界

贴代码

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[1200][1200];//地图
int vis[1200][1200];//记录每一步走到所加之和
int maxn=INT_MIN;//记录是否访问过
int dir[3][2]={{0,1},{1,0},{-1,0}};//上，下，右
void dfs(int x,int y){
    if(x<1||y<1||x>n||y>m){//判断越界
        return;
    }
    else if(x==n&&y==m){//如果走到终点
        if(maxn<vis[x][y]){//判断是否比maxn大
            maxn=vis[x][y];//更新maxn值
        }
    }
    else{//搜索主程序
        for(int i=0;i<3;i++){
            if(vis1[x+dir[i][0]][y+dir[i][1]]==0){//如果没有访问过
                vis1[x+dir[i][0]][y+dir[i][1]]=1;
                vis[x+dir[i][0]][y+dir[i][1]]=vis[x][y]+a[x+dir[i][0]][y+dir[i][1]];
                dfs(x+dir[i][0],y+dir[i][1]);//搜索
                vis1[x+dir[i][0]][y+dir[i][1]]=0;
                vis[x+dir[i][0]][y+dir[i][1]]=vis[x][y];//回溯一步
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    vis[1][1]=a[1][1];//首位需要事先标记
    dfs(1,1);
    cout<<maxn;
    return 0;//别忘啦
}