虽然我知道这题不能dfs但我就想知道那5分为什么拿不到
如题,我用的DFS,但很奇怪的是剪枝之后那五分反而拿不到了,可能哪里逻辑有问题,代码如下:
#include<stdio.h>
#include<string.h>
int n,m,k;
int dir[3][2] = {1,0,-1,0,0,1};//三个方向
int map[1001][1001];//格子里的数字
int vis[1001][1001];//是否走过
int mmax[1001][1001];//走过每个格子的最大花费(就是这里有问题)
void dfs(int x,int y,int now){
if(now+map[x][y]<=mmax[x][y]){
//目前不超过最大话费
return;
}
else mmax[x][y] = now+map[x][y];
//if(x==n-1&&y==m-1)return;
int nx,ny;
for(int i = 0;i<3;i++){
nx = x+dir[i][0];
ny = y+dir[i][1];
if(nx>n-1||ny>m-1||nx<0||ny<0)continue;
if(vis[nx][ny]==1)continue;
else{
vis[nx][ny]=1;
dfs(nx,ny,now+map[x][y]);
//draw();
vis[nx][ny]=0;
}
}
}
int main(){
//for(int i = 0;i<1001;i++){
memset(mmax,128,sizeof(mmax));
scanf("%d%d",&n,&m);
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
scanf("%d",&map[i][j]);
}
}
vis[0][0] = 1;
dfs(0,0,0);
printf("%d",mmax[n-1][m-1]);
}
评测记录在这:20分记录
(还有很诡异的一点是我把
if(now+map[x][y]<=mmax[x][y]){
那里的<=换成<之后竟然多了5分,在这 谁能帮忙解释一下怎么回事啊,感激不尽