题目描述

走迷宫
只分享最暴力的做法（bfs）还可以带上路径

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
int map[100][100];
typedef pair<int,int>PII;
bool vis[100][100];
string s[100][100];
int main(){
    int n ,m;
    cin>>n>>m;
    for(int i =0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin>>map[i][j];
            if(map[i][j])vis[i][j]=true;
        }
    }
    int dx[] = {1,0,0,-1},dy[] = {0,-1,1,0};
    char ds[] = {'D','L','R','U'};
    //初始化
    queue<PII> q ; 
    q.push({0,0});
    s[0][0] = "";
    while(q.size()){
        PII t = q.front();
        q.pop();
        if(t.first == n&&t.second == m)break;
        //扩展
        for(int i = 0 ;i<4;i++){
            int x = t.first+dx[i],y = t.second+dy[i];
            if(x<n&&x>=0&&y<m&&y>=0&&vis[x][y] ==false){
                s[x][y] = s[t.first][t.second]+ds[i];
                vis[x][y] =true;
                q.push({x,y});
            }
        }

    }
    //cout<<s[n-1][m-1]<<endl;
    cout<<s[n-1][m-1].length()<<endl;
    return 0;
}