奶牛们去一个 � × � N×M 玉米迷宫, 2 ≤ � ≤ 300 , 2 ≤ � ≤ 300 2≤N≤300,2≤M≤300。 迷宫里有一些传送装置,可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用。 如果一头奶牛处在这个装置的起点或者终点,这头奶牛就必须使用这个装置。 玉米迷宫除了唯一的一个出口都被玉米包围。 迷宫中的每个元素都由以下项目中的一项组成: 玉米,# 表示,这些格子是不可以通过的。 草地,. 表示,可以简单的通过。 传送装置,每一对大写字母 � A 到 � Z 表示。 出口,= 表示。 起点, @ 表示 奶牛能在一格草地上可能存在的四个相邻的格子移动,花费 1 1 个单位时间。从装置的一个结点到另一个结点不花时间。c++
时间: 2023-06-24 15:04:55 浏览: 51
的代码如下:
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 310;
const int INF = 0x3f3f3f3f;
int n, m;
int sx, sy, ex, ey;
char maze[MAXN][MAXN];
int d[MAXN][MAXN];
bool vis[MAXN][MAXN];
struct Node {
int x, y;
};
vector<Node> teleporter[26];
void bfs(int x, int y) {
queue<Node> q;
q.push({x, y});
vis[x][y] = true;
d[x][y] = 0;
while (!q.empty()) {
Node u = q.front(); q.pop();
int ux = u.x, uy = u.y;
if (maze[ux][uy] == '=') {
ex = ux, ey = uy;
return;
}
if (maze[ux][uy] >= 'A' && maze[ux][uy] <= 'Z') {
int idx = maze[ux][uy] - 'A';
if (teleporter[idx][0].x != ux || teleporter[idx][0].y != uy) {
int tx = teleporter[idx][0].x, ty = teleporter[idx][0].y;
if (!vis[tx][ty]) {
vis[tx][ty] = true;
d[tx][ty] = d[ux][uy] + 1;
q.push({tx, ty});
}
} else {
int tx = teleporter[idx][1].x, ty = teleporter[idx][1].y;
if (!vis[tx][ty]) {
vis[tx][ty] = true;
d[tx][ty] = d[ux][uy] + 1;
q.push({tx, ty});
}
}
} else {
if (ux-1 >= 1 && maze[ux-1][uy] != '#' && !vis[ux-1][uy]) {
vis[ux-1][uy] = true;
d[ux-1][uy] = d[ux][uy] + 1;
q.push({ux-1, uy});
}
if (uy-1 >= 1 && maze[ux][uy-1] != '#' && !vis[ux][uy-1]) {
vis[ux][uy-1] = true;
d[ux][uy-1] = d[ux][uy] + 1;
q.push({ux, uy-1});
}
if (ux+1 <= n && maze[ux+1][uy] != '#' && !vis[ux+1][uy]) {
vis[ux+1][uy] = true;
d[ux+1][uy] = d[ux][uy] + 1;
q.push({ux+1, uy});
}
if (uy+1 <= m && maze[ux][uy+1] != '#' && !vis[ux][uy+1]) {
vis[ux][uy+1] = true;
d[ux][uy+1] = d[ux][uy] + 1;
q.push({ux, uy+1});
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> maze[i][j];
if (maze[i][j] == '@') sx = i, sy = j;
if (maze[i][j] >= 'A' && maze[i][j] <= 'Z') teleporter[maze[i][j]-'A'].push_back({i, j});
}
}
bfs(sx, sy);
cout << d[ex][ey] << endl;
return 0;
}