题目描述

http://lx.lanqiao.cn/problem.page?gpid=T291

算法1

(暴力枚举) $O(n^2)$

参考了 庶 大佬。

C++ 代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

typedef pair<int,int> PII;

const int N=510;
char g[N][N];
bool st[N][N];
int pre[4][2]={1,0,0,-1,0,1,-1,0};
char os[5]="DLRU";  //记录方案，并且求方案数 
int n,m;            //虽然一个点可以转移到多个点，但是每个点只能由一个点转移而来（多个则取最近的，也就是第一次到达），所以可以记录pre数组来记录方案数 
pair<PII, char> path[N][N];

void bfs()
{

    st[0][0]=true;

    queue<PII> q;
    q.push({0,0});

    memset(path,-1,sizeof path);

    while(q.size())
    {        
        PII t=q.front();
        q.pop();
        if(t.first==n-1 && t.second==m-1) break;
        for(int i=0;i<4;i++)
        {
            int x1,y1;
            x1=t.first+pre[i][0];
            y1=t.second+pre[i][1];

            if(x1<0 || x1>=n || y1<0 || y1>=m) continue;
            if(g[x1][y1]=='1') continue;
            if(st[x1][y1]) continue;

            st[x1][y1]=true;
            path[x1][y1].first=t,path[x1][y1].second=os[i];
            q.push({x1,y1});
        }
    }


    vector<char> way;
    int x=n-1,y=m-1;        //从终点开始逆序 
    while(x!=0 || y!=0)
    {
        way.push_back(path[x][y].second);
        PII t=path[x][y].first;
        x=t.first,y=t.second;
    }
    reverse(way.begin(),way.end());
    cout<<way.size()<<endl;
    for(int i=0;i<way.size();i++)
    {
        cout<<way[i];
    }
}

int main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++)
    {
        scanf("%s",g[i]);
    }

    bfs();

    return 0;

}