迷宫-蓝桥-迷宫-BFS-DFS

很久没有认真的写一道DFS和BFS的题了 今天早上这个题花了1个多小时，竟然还没对。 答案一直出错，我都快崩溃了，那么简单的题。。。我TM 晚上又重写了一遍，答案对了。但是还是不知道为什么早上的错了。也没留备份。。

算是一个标准的BFS模板题

#include <iostream> #include <vector> #include <queue> using namespace std; const int dx[4] = {1, 0, 0, -1}; const int dy[4] = {0, -1, 1, 0}; char ct[4] = {'D', 'L', 'R', 'U'}; // 和dx，dy的下标对应。方便下面的转化 int N, M; // BFS用 struct node { int x, y; string c; }; int dp[100][100]; string rode[100]; // DFS用 int mincnt = 100000; string ans; void dfs(int x, int y, string s, int cnt) { // 如果比之前最短的长，就么有必要继续了 if (cnt > mincnt) return; if (x == N - 1 && y == M - 1) { // 我惊奇的发现 直接 ans = min(ans, s); // 竟然不行，，min不根据长度来比较 if (cnt < mincnt) { mincnt = cnt; ans = s; } else if (cnt == mincnt) { ans = min(ans, s); } return; } for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < N && ny >= 0 && ny < M && rode[nx][ny] == '0' && !dp[nx][ny]) { dp[nx][ny] = 1; dfs(nx, ny, s + ct[i], cnt + 1); dp[nx][ny] = 0;// 还原 } } } void bfs() { queue<node> q; q.push({0, 0, ""}); dp[0][0] = 1; while (!q.empty()) { auto e = q.front(); q.pop(); if (e.x == N - 1 && e.y == M - 1) { cout << e.c; return; } for (int i = 0; i < 4; i++) { int nx = e.x + dx[i]; int ny = e.y + dy[i]; if (nx >= 0 && nx < N && ny >= 0 && ny < M && rode[nx][ny] == '0' && !dp[nx][ny]) { dp[nx][ny] = 1; q.push({nx, ny, e.c + ct[i]}); } } } } int main() { cin >> N >> M; for (int i = 0; i < N; i++) { cin >> rode[i]; } dp[0][0] = 1; // dfs(0, 0, "", 0); bfs(); cout << ans; return 0; }