79是深搜的极限了吗……
查看原帖
79是深搜的极限了吗……
316681
zhongshizhao1楼主2023/5/27 15:54
#include <iostream>
#include <cstring>
using namespace std;
int n,m,zx,zy,smax=1000000,sum=0;
int movei=-1,movej=-1;
char a[505][505];
int bz[505][505];
int f[505][505];
int dx[4]={0,1,0,-1},
	dy[4]={1,0,-1,0};
bool flag=0;
bool doit(int p,int q,char b)
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(a[i][j]==b&&(i!=p||j!=q))
			{
				movei=i;
				movej=j;
				return 1;
			}
		}
	}
	return 0;
}
void dfs(int p,int q)
{
	int x,y;
	if(sum>=f[p][q]&&(a[p][q]<'A'||a[p][q]>'Z'))
	{
		return;
	}
	if(a[p][q]<'A'||a[p][q]>'Z')
	{
		f[p][q]=sum;
	}
	if(a[p][q]<'A'||a[p][q]>'Z')
	{
		bz[p][q]=1;
	}
	if(p==zx&&q==zy)
	{
		if(sum<smax)
		{
			smax=sum;
		}
		return;
	}
	for(int i=0;i<4;i++)
	{
		x=p+dx[i];
		y=q+dy[i];
		if(x>=0&&x<n&&y>=0&&y<m&&bz[x][y]==0&&a[x][y]!='#')
		{
			sum++;
			if(a[x][y]>='A'&&a[x][y]<='Z')
			{
				if(doit(x,y,a[x][y])==1)
				{
					bz[x][y]=1;
					dfs(movei,movej);
					bz[x][y]=0;	
					sum--;
				}
				else
				{
					dfs(x,y);
					bz[x][y]=0;
					sum--;
				}
			}
			else
			{
				dfs(x,y);
				bz[x][y]=0;
				sum--;
			} 
			
		}
	}
}
int main()
{
	int sx,sy,ji=0;
	
	memset(f,0xaa7f,sizeof(f));
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>a[i][j]; 
			if(a[i][j]=='@')
			{
				sx=i;
				sy=j;
			}
			else if(a[i][j]=='=')
			{
				zx=i;
				zy=j;
			}
		}
	}
	dfs(sx,sy);
	cout<<smax<<endl;
	return 0;
}
2023/5/27 15:54
加载中...