dfs求助
查看原帖
dfs求助
65809
Yuicream楼主2020/9/30 15:50
#include<iostream>
using namespace std;
char map[400][400];
int pd[400][400];
int bx,by,ex,ey,mintime=0x7ffff,nx,ny,tpx[100][2],tpy[200][2],tptot[200],n,m;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
void dfs(int x,int y,int time);
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>map[i][j];
			if(map[i][j]=='@'){
				bx=i; by=j;
			}
			else if(map[i][j]=='='){
				ex=i; ey=j;
			}
			else if(map[i][j]!='#'&&map[i][j]!='.'){
				tpx[(int)map[i][j]][tptot[(int)map[i][j]]]=i;
				tpy[(int)map[i][j]][tptot[(int)map[i][j]]]=j;
				tptot[(int)map[i][j]]++;
			}
		}
	}
	dfs(bx,by,0);
	cout<<mintime;
	return 0;
}
void dfs(int x,int y,int time)
{
	if(x==ex&&y==ey)
	{
		mintime=(mintime<time?mintime:time);
		return;
	}
	pd[x][y]++;
	for(int i=0;i<4;i++)
	{
		nx=x+dx[i]; ny=y+dy[i];
		if(nx>0&&nx<=n&&ny>0&&ny<=m)
		{
			if(map[nx][ny]!='#'&&map[nx][ny]!='='&&map[nx][ny]!='.'&&pd[nx][ny]<=2)
			{
				if(nx==tpx[(int)map[nx][ny]][0]&&ny==tpy[(int)map[nx][ny]][0]){
					pd[nx][ny]++;
					dfs(tpx[(int)map[nx][ny]][1],tpy[(int)map[nx][ny]][1],time+1);
					pd[nx][ny]--;
				}
				else{
					pd[nx][ny]++;
					dfs(tpx[(int)map[nx][ny]][0],tpy[(int)map[nx][ny]][0],time+1);
					pd[nx][ny]--;
				}
			}
			if(map[nx][ny]=='.'||map[nx][ny]=='@'||map[nx][ny]=='=')
			{
				if(pd[nx][ny]==0)
					dfs(nx,ny,time+1);
			}
		}
	}
	pd[x][y]--;
}

37分 WA了两个点 剩下的点TLE

2020/9/30 15:50
加载中...