dfs 80pts,#1TLE卡死循环,#12WA求助
  • 板块P2802 回家
  • 楼主luqyou
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/8/4 14:41
  • 上次更新2023/10/27 17:04:10
查看原帖
dfs 80pts,#1TLE卡死循环,#12WA求助
464732
luqyou楼主2022/8/4 14:41
#include<bits/stdc++.h>
using namespace std;
int n,m,puck[11][11],sx,sy,ex,ey,ans=2147483647,vis[11][11];
int dx[]={0,0,0,-1,1};
int dy[]={0,-1,1,0,0};
void dfs(int x,int y,int health,int step){
	//for(int i=1;i<step;i++) printf("	");
	//printf("(%d,%d,health:%d):{\n",x,y,health);
	if(health==0){
		return ;
	}
	if(step>=ans){
		return ;
	}
	if(puck[x][y]==4){
		health=6;
	}
	if(x==ex&&y==ey){
		ans=step;
		return ;
	}
	for(int i=1;i<=4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(nx&&ny&&nx<=n&&ny<=m&&!vis[nx][ny]&&puck[nx][ny]){
			//for(int i=1;i<=step;i++) printf("	");
			//printf("(%d,%d,health:%d)\n",nx,ny,health-1);
			vis[nx][ny]=1;
			dfs(nx,ny,health-1,step+1);
			vis[nx][ny]=0;
		}
	}
	//for(int i=1;i<step;i++) printf("	");
	//printf("}\n");
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&puck[i][j]);
			if(puck[i][j]==2){
				sx=i;
				sy=j;
			}
			if(puck[i][j]==3){
				ex=i;
				ey=j;
			}
		}
	}
	vis[sx][sy]=1;
	dfs(sx,sy,6,0);
	printf("%d",ans==2147483647?-1:ans);
	return 0;
}
2022/8/4 14:41
加载中...