迷宮-藍橋-迷宮-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;
}