较普通的走迷宫的题
传送门 ：codevs 2059 逃出克隆岛
思路 ：BFS 即可 PS ：传送门 不必重复使用
#include <iostream> #include <cstdio> #define Max 2020 using namespace std; int N, M; int start_x, start_y, end_x, end_y; int move_x [5] = {1, -1, 0, 0}, move_y [5] = {0, 0, 1, -1}; char map [Max][Max]; int queue [Max][3]; int cost [Max * 10]; bool door [Max][Max], visit [Max][Max]; bool flag; int pay; void BFS (int start_x, int start_y) { int head_cur = 0, tail_cur = 1; visit [start_x][start_y] = true; //标记当前点为 已访问 queue [1][1] = start_x; //将起点入队列 queue [1][2] = start_y; cost [1] = 0; // 当前的花费为0 while (head_cur < tail_cur) { head_cur++; for (int i = 0; i <= 3; i++) { int x = queue [head_cur][1] + move_x [i]; int y = queue [head_cur][2] + move_y [i]; if (x == end_x && y == end_y) // 如果到达了终点， flag 标记为 true 直接输出花费即可 { flag = true; cout << cost [head_cur]; return; } if (x > 0 && x <= N && y > 0 && y <= M && map [x][y] != '#' && visit [x][y] == false) // 在边界内，且当前点 不是障碍点 且当前点未访问 { if (door [x][y] == true) //如果此点为传送门，且当前传送门可以走 { door [x][y] = false; // 标记为已走 for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) //在全图内搜索 可走的传送门 if (door [i][j] == true) { tail_cur++; queue [tail_cur][1] = i; //将当前传送到的位置加入队列 queue [tail_cur][2] = j; door [i][j] = false; // 标记此传送门为已走 cost [tail_cur] = cost [head_cur]; //由于传送门没有花费， 所以等于前一个点的花费 } } tail_cur++; // 如果不是传送门 ，将当前位置加入队列 queue [tail_cur][1] = x; queue [tail_cur][2] = y; visit [x][y] = true; // 标记为已访问 if (map [x][y] == '*') //如果走此点需要花费 cost [tail_cur] = cost [head_cur] + pay; // 上一个点的花费 再加一次花费 即为当前位置的花费 else cost [tail_cur] = cost [head_cur]; // 若是普通点，则当前点的花费等于上一个点的花费 } } } } int main() { ios :: sync_with_stdio (false); cin >> N >> M >> pay; for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) { cin >> map [i][j]; if (map [i][j] == 'Y') // 记录起点 { start_x = i; start_y = j; } else if (map [i][j] == 'C') //记录终点 { end_x = i; end_y = j; } else if (map [i][j] == 'P') //记录传送门的位置 标记当前传送门可访问 door [i][j] = true; } BFS (start_x, start_y); if (flag == false) // 若走不通 cout << "screw you!"; return 0; }