#include<iostream> #include<queue> #include<string> using namespace std; const int maxsize = 310; int n, m; struct door{ int x; int y; int t; }; queue<door> q; int vis[maxsize][maxsize]; int dir[4][2] = { {1, 0}, {-1, 0}, {0, -1}, {0, 1} }; char map[maxsize][maxsize]; bool judge(door a) { if (a.x >= 0 && a.x < n && a.y >= 0 && a.y < m && !vis[a.x][a.y] && map[a.x][a.y] != '#') return true; return false; } void fly1(door& a) { for (int k = 0; k < n; k++) for (int z = 0; z < m; z++) if (map[k][z] == map[a.x][a.y] && (k != a.x || z != a.y)) { a.x = k, a.y = z; q.push(a); return; } } int main() { cin >> n >> m; door temp; string s = ""; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; if (map[i][j] == '@') temp.x = i, temp.y = j, temp.t = 0; } } q.push(temp),vis[temp.x][temp.y] = 1; while (!q.empty()) { door tem = q.front(); q.pop(); if (map[tem.x][tem.y] == '=') { cout << tem.t; return 0; } if (map[tem.x][tem.y] >= 'A' && map[tem.x][tem.y] <= 'Z') fly1(tem); for (int i = 0; i < 4; i++) { int dx = tem.x + dir[i][0], dy = tem.y + dir[i][1]; door a = {dx, dy, tem.t}; if (judge(a)) { a.t = tem.t + 1; q.push(a), vis[a.x][a.y] = 1; } } } return 0; }
时间: 2023-06-25 15:02:30 浏览: 138
#include <iostream>
这是一段C++代码,实现了一个迷宫问题的求解。具体来说,代码中定义了一个door结构体,表示迷宫中的门,其中包含了门所在的位置和到达该门的时间。代码使用了BFS算法,从起点开始搜索,依次遍历每个可达位置,并将可达位置加入队列中进行下一步搜索。在搜索过程中,如果遇到了门,则需要将门对应的另一个位置作为下一个搜索的起点。直到搜索到终点,程序输出所需的最短时间。
需要注意的是,代码中使用了一个二维数组vis来记录每个位置是否已经被访问过,避免重复访问。同时,由于迷宫中可能存在多个门,因此当搜索到门时,需要使用fly1函数将门对应的另一个位置作为下一个搜索的起点,而不能直接使用当前门所在的位置。
阅读全文