DFS-19pts求优化
查看原帖
DFS-19pts求优化
481621
Zhang_Wenjie楼主2022/10/2 11:18

AC#1,#5,#14,TLE#6,#13,#15,#16,其他WA了。

#include<bits/stdc++.h>
using namespace std;
const int N=310;
int n,m,sx,sy,ans=N*N+10;
char Map[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool vis[N][N];
void dfs(int x,int y,int step)
{
	if(Map[x][y]=='=')
	{
		ans=min(ans,step);
		return;
	}
	for(int i=0;i<4;i++)
	{
		int tx=x+dx[i],ty=y+dy[i];
		if((tx>=1&&tx<=n&&ty>=1&&ty<=m) && !vis[tx][ty] && Map[tx][ty]!='#')
		{
			
			if(Map[tx][ty]=='.'||Map[tx][ty]=='=')
			{
				vis[tx][ty]=true;
				dfs(tx,ty,step+1);
				vis[tx][ty]=false;
			}
			else 
			{
				for(int i=1;i<=n;i++)
					for(int j=1;j<=n;j++)
					{
						if(i!=tx && j!=ty && Map[i][j]==Map[tx][ty])
						{
							vis[i][j]=true;
							vis[tx][ty]=true;
							dfs(i,j,step+1);
							vis[tx][ty]=false;
							vis[i][j]=false;
						}
					}
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		for(int j=0;j<s.size();j++) 
		{
			Map[i][j+1]=s[j];
			if(s[j]=='@') sx=i,sy=j+1;
		}
	}
	vis[sx][sy]=true;
	dfs(sx,sy,0);
	printf("%d\n",ans);
	return 0;
}
2022/10/2 11:18
加载中...