60pts求调
查看原帖
60pts求调
777764
违规用户名777764楼主2024/9/30 13:37
#include <iostream>
#include <queue>
#define int long long
using namespace std;

int n, m;
int x1, y1, x2, y2;
bool vis[510][510];
char g[510][510];

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

struct stu
{
	int step, x, y;
} ;

int bfs()
{
	deque<stu> dq;
	dq.push_front({0, x1, y1});
	while (!dq.empty())
	{
		stu u = dq.front();
		dq.pop_front();
		if (u.x == x2 && u.y == y2)
			return u.step;
		if (vis[u.x][u.y])
			continue;
		vis[u.x][u.y] = 1;
		for (int i = 0; i < 4; ++i)
		{
			int nx = u.x + dx[i], ny = u.y + dy[i];
			if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
			if (g[nx][ny] == g[u.x][u.y])
				dq.push_front({u.step, nx, ny});
			dq.push_back({u.step + 1, nx, ny});
		}
	}
	return -1;
}

signed main()
{
	while (cin >> n >> m)
	{
		if (n == m && m == 0)
			break;
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j)
				cin >> g[i][j];
		cin >> x1 >> y1 >> x2 >> y2;
		++x1, ++y1, ++x2, ++y2;
		cout << bfs() << endl;
	}
	return 0;
}
2024/9/30 13:37
加载中...