dfs20分求调!!
查看原帖
dfs20分求调!!
538085
liysjianttso楼主2023/5/21 17:37

虽然我知道这题不能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分,在这 谁能帮忙解释一下怎么回事啊,感激不尽

2023/5/21 17:37
加载中...