大佬求助,WA了3和7,实在调试不出来了
查看原帖
大佬求助,WA了3和7,实在调试不出来了
1488153
wostcDk楼主2025/1/23 18:09
//P1825 [USACO11OPEN] Corn Maze S
#include<iostream>
#include<algorithm>
#include<cstring>
#include <utility>
#include<cmath>

using namespace std;

typedef pair<int, int> PII;
const int N = 310;

int n, m;
int x1, y11, x2, y2;
char g[N][N];
int dist[N][N];
bool st[N][N];
PII q[N * N];

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

PII tran(PII q1,char pd)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (g[i][j] == pd && (q1.first != i || q1.second != j))
			{
				return { i,j };
			}
		}
	}
	return q1;
}

int bfs()
{
	memset(dist, -1, sizeof(dist));
	q[0] = { x1,y11 };
	dist[x1][y11] = 0;
	int head = 0, end = 0;

	while (head <= end)
	{
		auto t = q[head++];

		for (int i = 0; i < 4; i++)
		{
			int a = t.first + dx[i], b = t.second + dy[i];

			if (a<1 || a>n || b<1 || b>m)continue;
			if (g[a][b] == '#')continue;
			if (st[a][b])continue;
			//if (dist[a][b]>=0)continue;
			if (g[a][b] >= 'A' && g[a][b] <= 'Z')
			{

				PII c = { a,b };
				auto d = tran(c,g[a][b]);
				a = d.first, b = d.second;
			}
			dist[a][b] = dist[t.first][t.second] + 1;
			q[++end] = { a,b };
			st[a][b] = true;
			if (g[a][b] >= 'A' && g[a][b] <= 'Z')
				st[a][b] = false;
			if (g[a][b] == '=')
				return dist[a][b];
		}
	}
}

int main()
{
	cin >> n >> m;
	//memset(g, 35, sizeof(g));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> g[i][j];
			if (g[i][j] == '@')
			{
				x1 = i, y11 = j;
			}
			if (g[i][j] == '=')
			{
				x2 = i, y2 = j;
			}
		}
	}
	int res = bfs();
	cout << res;

	return 0;
}
2025/1/23 18:09
加载中...