19分求调
查看原帖
19分求调
735797
XingnoYi楼主2024/10/22 19:20
#include <iostream>
#include <queue>
#define big long long
using namespace std;
char mp[400][400];
big n,m,vis[400][400];
big f[4][2] = {{1,0},{0,1},{0,-1},{-1,0}};
struct Node{
	big x,y,step;
}pos,tmp;
queue <Node> q;
void find(char c,big &x,big &y)
{
	for(big i = 1;i <= n;i++)
	{
		for(big j = 1;j <= m;j++)
		{
			if(mp[i][j] == c && (i != x || j != y))
			{
				x = i, y = j;
				return;
			}
		}
	}
}
big bfs()
{
	q.push(pos);
	vis[pos.x][pos.y] = 1;
	while(!q.empty())
	{
		pos = q.front(), q.pop();
		if(mp[pos.x][pos.y] == '=')
		{
			return pos.step;
		}
		if(mp[pos.x][pos.y] >= 'A' && mp[pos.x][pos.y] <= 'Z');
		{
			find(mp[pos.x][pos.y],pos.x,pos.y);
		}
		for(big i = 0;i < 4;i++)
		{
			big xx = pos.x+f[i][0], yy = pos.y+f[i][1];
			if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && mp[xx][yy] != '#' && !vis[xx][yy])
			{
				if(!(mp[xx][yy] >= 'A' && mp[xx][yy] <= 'Z'))
				{
					vis[xx][yy] = 1;
				}
				q.push((Node){xx,yy,pos.step+1});
			} 
		}
	}
	return 0;
}
int main()
{
	cin >> n >> m;
	for(big i = 1;i <= n;i++)
	{
		for(big j = 1;j <= m;j++)
		{
			cin >> mp[i][j];
			if(mp[i][j] == '@')
			{
				pos = (Node){i,j,0};
			}
		} 
	}
	cout << bfs();
	return 0;
}

2024/10/22 19:20
加载中...