算法提高 学霸的迷宫

   

时间限制：1.0s   内存限制：256.0MB

    

问题描述

　　学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。

输入格式

　　第一行两个整数n， m，为迷宫的长宽。
　　接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。

输出格式

　　第一行一个数为需要的最少步数K。
　　第二行K个字符，每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。

样例输入

Input Sample 1:
3 3
001
100
110

Input Sample 2:
3 3
000
000
000

样例输出

Output Sample 1:
4
RDRD

Output Sample 2:
4
DDRR

数据规模和约定

　　有20%的数据满足：1<=n,m<=10
　　有50%的数据满足：1<=n,m<=50
　　有100%的数据满足：1<=n,m<=500。

迷宫问题可以广搜和深搜：广搜可以求解最短的路径，深搜只是尽快找到一条路径就停止了。

另外深搜用递归的时候，层数一多就不行了，可以用栈来写。广搜可以用队列来存储。

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#define FOR(i,x,n) for(int i=x;i<n;i++)
#define ll long long int
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define MAX_N 50005

using namespace std;

struct node{
    int x,y;
    int steps;
    string path;
};

int N,M;
char maze[555][555];
int dirX[4]={1,0,0,-1};//D,L,R,U
int dirY[4]={0,-1,1,0};
char dir[4]={'D','L','R','U'};

bool check(node a){
    if(a.x>=0&&a.x<=N-1&&a.y>=0&&a.y<=M-1&&maze[a.x][a.y]=='0'){
        return true;
    }else{
        return false;
    }
}

void bfs(){
    queue<node> q;
    node now;
    now.x=0;now.y=0;
    now.steps=0;
    q.push(now);
    while(!q.empty()){
        node t=q.front();q.pop();
        FOR(i,0,4){
            node next=t;
            next.x+=dirX[i];next.y+=dirY[i];
            next.steps++;
            next.path+=dir[i];
            if(next.x==N-1&&next.y==M-1){
                printf("%d\n",next.steps);
                //printf("%s",next.path);
                cout<<next.path<<endl;
                return ;
            }else{
                if(check(next)){
                    q.push(next);
                    maze[next.x][next.y]=1;
                    continue;
                }else{
                    if(next.x>=0&&next.x<=N-1&&next.y>=0&&next.y<=M-1){
                        maze[next.x][next.y]=1;
                    }
                }

            }
        }
    }
}

int main()
{
    //freopen("data.txt", "r", stdin);
    //freopen("data.out", "w", stdout);
    scanf("%d %d",&N,&M);
    getchar();
    FOR(i,0,N){
        FOR(j,0,M){
            scanf("%c",&maze[i][j]);
        }
        getchar();
    }
    bfs();
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}