BFS 80分求调
  • 板块学术版
  • 楼主wangqz
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/11/19 10:20
  • 上次更新2023/10/27 02:26:19
查看原帖
BFS 80分求调
530676
wangqz楼主2022/11/19 10:20

1 1

#include<iostream>
#include<cstdio>
using namespace std;
const int size=105;
int n,m;
char c;
int f[size][size];
int map[size][size];
int p[11111][5];
int tail=1,head=0;
int k;
int dx[4]={0,1,0,-1},
	dy[4]={1,0,-1,0};
int main()
{	
	freopen("way.in","r",stdin);
	freopen("way.out","w",stdout);
	cin>>n>>m;

	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)  
		{
			cin>>c;
			if(c>='A'&&c<='Z')
				f[i][j]=(int)c;
			else 
				f[i][j]=c-48;
			map[i][j]=f[i][j];
		}
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=m;j++) 
//			cout<<a[i][j];
//		cout<<endl;
//	}		 
	p[1][1]=1;p[1][2]=1;p[1][3]=0;f[1][1]=1;
	while(head<tail)
	{
		head++;
		for(int i=0;i<=3;i++)
		{
			int x=p[head][1]+dx[i];
			int y=p[head][2]+dy[i];
			if(x>=1&&y>=1&&x<=n&&y<=m)
			{
				if(f[x][y]==0)
				{
					tail++;
					p[tail][1]=x;
					p[tail][2]=y;
					p[tail][3]=p[head][3]+1;
					f[x][y]=1;
					if(x==n&&y==m)
					{  
						cout<<p[tail][3];
						return 0;
					}
				}
				else if(f[x][y]>1)
				{
					int xx,yy;
					k=0;		
					for(xx=1;xx<=n;xx++)
					{
						for(yy=1;yy<=m;yy++)
							if(map[xx][yy]==map[x][y]&&xx!=x&&yy!=y)
							{
								tail++;
								k=1;
								break;
							}
						if(k=	=1)	
							break;
					}
					f[x][y]=1;
					p[tail][1]=xx;
					p[tail][2]=yy;
					p[tail][3]=p[head][3]+1;
				}
			}
		}
	}
	cout<<"No Solution.";
	return 0;
}
/*
3 4	
0000
00A0
A000
*/
2022/11/19 10:20
加载中...