返回题解分享
讨论 / 题解分享/ 帖子详情

迷宫(结果填空) - 题解

#include <bits/stdc++.h>

using namespace std;

const int N = 55;

int n, m;
char g[N][N];
int dx[4] = {1, 0, 0, -1}, dy[4] = {0, -1, 1, 0};
string mp[4] = {"D", "L", "R", "U"};
string ans[N][N];
bool st[N][N];

string bfs()
{
    queue<pair<int, int>> q;
    q.push({0, 0});
    st[0][0] = true;
    ans[0][0] = "";

    while (q.size())
    {
        auto t = q.front();
        if (t.first == n - 1 && t.second == m - 1)
            return ans[t.first][t.second];
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            int tx = t.first + dx[i], ty = t.second + dy[i];
            if (tx >= 0 && tx < n && ty >= 0 && ty < m && g[tx][ty] == '0' && !st[tx][ty])
            {
                st[tx][ty] = true;
                ans[tx][ty] = ans[t.first][t.second] + mp[i];
                q.push({tx, ty});
            }
        }
    }
    return "";
}

int main()
{
    freopen("input.txt", "r", stdin);
    n = 30, m = 50;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> g[i][j];

    cout << bfs() << endl;

    return 0;
}
0 回复 0 转发 1 喜欢 0 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!