58分c++宽搜求调
查看原帖
58分c++宽搜求调
810054
suzichen03楼主2023/5/10 20:23
#include<iostream>
using namespace std;
int n,m;
char a[301][301];
int vis[301][301];
struct Node
{
	int x;
	int y;
	int step;
};
Node q[1000001];
bool isOK(int newx,int newy)
{
	if(newx>=1&&newx<=n&&newy>=1&&newy<=m)
	{
		return true;
	}
	else
	{
		return false;
	}
}
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};
Node chuansong(char v,int x)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]==v&&vis[i][j]==0)
			{
				Node node;
				node.x=i;
				node.y=j;
				node.step=x+1;
				return node;
			}
		}
	}
	Node node; 
	node.x=0;
	node.y=0;
	node.step=-1;
	return node;
}
int f(Node node)
{
	int head=1;
	int tail=1;
	q[tail]=node;
	vis[node.x][node.y]=1;
	Node cur;
	while(head<=tail)
	{
		
		cur=q[head];
//		cout<<cur.x<<" "<<cur.y<<" "<<cur.step<<endl;
		head++;
		if(a[cur.x][cur.y]=='=')
		{
			return cur.step;
		}
		for(int i=1;i<=n;i++)
		{
			int newx=cur.x+dx[i];
			int newy=cur.y+dy[i];
			if(isOK(newx,newy)==true&&a[newx][newy]!='#'&&vis[newx][newy]==0)
			{
				if(a[newx][newy]!='.'&&a[newx][newy]!='='&&a[newx][newy]!='@')
				{
					vis[newx][newy]=1;
					if(chuansong(a[newx][newy],cur.step).step!=-1)
					{
						tail++;
						q[tail]=chuansong(a[newx][newy],cur.step);
					}
				}
				else
				{
					tail++;
					q[tail].x=newx;
					q[tail].y=newy;
					q[tail].step=cur.step+1;
					vis[newx][newy]=1;
				}
			}
		}
	}
	return -1;
}
int main()
{
	int fx,fy;
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin >> a[i][j];
			if(a[i][j]=='@')
			{
				fx=i;
				fy=j;
			}
		}
	}
	Node node;
	node.x=fx;
	node.y=fy;
	node.step=0;
	cout << f(node);
	return 0;
}
2023/5/10 20:23
加载中...