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

迷宫(结果填空) - 题解

#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};
int dy[4]={0,-1,1,0};
char 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.empty())
    {
        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()
{
    n=30,m=50;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>g[i][j];
        }
    }
    cout<<bfs();
    return 0;
}
0 回复 0 转发 0 喜欢 7 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!