38分求助大佬求调
查看原帖
38分求助大佬求调
1350908
gjrBJ楼主2024/9/5 17:31
#include<bits/stdc++.h>
using namespace std;
struct p {
	int x, y;
};
int n, m, sx, sy, tx, ty, ans[310][310], vis[310][310];//行数列数和起点终点坐标和答案数组和标记数组
int dx[] = {1, 0, 0, -1};
int dy[] = {0, 1, -1, 0};
char s[310][310];//网格
void bfs() {
	queue<p> q;
	vis[sx][sy] = 1;
	ans[sx][sy] = 0;
	q.push({sx, sy});
	while (!q.empty()) {
		p g = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			p nw = {g.x + dx[i], g.y + dy[i]};
			if (nw.x >= 1 && nw.x <= n && nw.y >= 1 && nw.y <= m) {
				if (vis[nw.x][nw.y] == 0 && s[nw.x][nw.y] >= 'A' && s[nw.x][nw.y] <= 'Z') {
					ans[nw.x][nw.y] = ans[g.x][g.y] + 1;
					vis[nw.x][nw.y] = 1;
					q.push(nw);
					for (int j = 1; j <= n; j++) {
						for (int k = 1; k <= m; k++) {
							if (s[j][k] == s[nw.x][nw.y]) {
								ans[j][k] = ans[nw.x][nw.y];
								vis[j][k] = 1;
								q.push({j, k});
							}
						}
					}
					continue;
				}
				if (vis[nw.x][nw.y] == 0 && s[nw.x][nw.y] != '#') {
					if (s[nw.x][nw.y] == '.') {
						ans[nw.x][nw.y] = ans[g.x][g.y] + 1;
						vis[nw.x][nw.y] = 1;
						q.push(nw);
					} else if (s[nw.x][nw.y] == '=') {
						ans[nw.x][nw.y] = ans[g.x][g.y] + 1;
						vis[nw.x][nw.y] = 1;
						return ;
					}
				}
			}
		}
	}
}
int main() {
	memset(ans, -1, sizeof(ans));
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> s[i][j];
			if (s[i][j] == '@') {
				sx = i, sy = j;
			}
			if (s[i][j] == '=') {
				tx = i, ty = j;
			}
		}
	}
	bfs();
	cout << ans[tx][ty];
	return 0;
}

思路:不是传送门就普通广搜,否则找另一个搜

2024/9/5 17:31
加载中...