bfs求助
查看原帖
bfs求助
494421
Exoplanet楼主2023/2/18 11:06

样例也过不去。

#include<cstdio>
#include<cstring>
using namespace std;
int n,m; 
int c1,d1;
char a[301][301];
int vis[301][301];
int x;
int y;
int e[4]={0,0,1,-1};
int r[4]={1,-1,0,0};
struct s
{
	int qd,zd,bs;
}ans[100000];
int fy(int q,int w)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[q][w]==a[i][j]&&(q!=i||w!=j))
			{
				x=i;
				y=j;
				return 0;
			}
		}
	}
}
int bfs()
{
	int head=0,tail=1;
	do{
        head++;
        if(a[ans[head].qd][ans[head].zd]>='A'&&a[ans[head].qd][ans[head].zd]<='Z')
        {
                fy(ans[head].qd,ans[head].zd);
                ans[head].qd=x;
                ans[head].zd=y;
        } 
        for(int i=0;i<4;i++)
        {
            int hzb=ans[head].qd+e[i];
            int zzb=ans[head].zd+r[i];
            if(vis[hzb][zzb]==0&&a[hzb][zzb]!='#')
            {
                vis[hzb][zzb]=1;
                tail++;
                ans[tail].qd=hzb;
                ans[tail].zd=zzb;
                ans[tail].bs++;
                if(ans[tail].qd==c1&&ans[tail].zd==d1)
                {
                    printf("%d\n",ans[tail].bs);
                    return 0;
                }
            }
        }
	}while(head<tail);	
}
int main()
{
	int q,d;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=m;j++)
    	{
    		scanf(" %c",&a[i][j]);
    		if(a[i][j]=='@')
    		{
    			q=i;d=j;
			}
			if(a[i][j]=='=')
			{
				c1=i;d1=j;
			}
		}
    }
    //printf("3");
	vis[q][d]=1;
	ans[1].qd=q;
	ans[1].zd=d;
	bfs();	
	return 0;
} 

谢谢各位愿意看的大佬。

2023/2/18 11:06
加载中...