试题 算法提高 学霸的迷宫
提交此题 评测记录
资源限制
时间限制：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。
解题思路：典型的BFS最优解问题，除了常规的广搜操作，题目还要求输出每一步走的方向，也就是要存放当前遍历到的节点的父节点，这里我开了一个二维的结构体数组（当然也可以用vector链表）。经BFS函数操作得到最后更新过的坐标为（n,m）的格子，再向前遍历，用一个findDir函数找出其相对父节点的方向，并存放到栈里面。最后输出栈中的元素，就得到了，从（1，1）到（n,m）走的每一步的方向。
代的码如下：
#include <iostream>
#include <string.h>
#include <queue>
#include <sstream>
#include <stack>
using namespace std;
typedef struct Box *Ftr;
struct Box{
int r,c;
int fr,fc;
int steps;
Box(){ }
Box(int rr,int cc,int ffr=0,int ffc=0,int st=0):r(rr),c(cc),fr(ffr),fc(ffc),steps(st) { }
}GG[506][506];
int G[506][506];
int visited[506][506];
int n,m;
queue<Box> Q;
void ReadInput(){
cin>>n>>m;
string data;
for(int i=1;i<=n;i++){
cin>>data; //输入得做优化， 切割字符串
for(int j=1;j<=m;j++){
G[i][j]=data[j-1]-'0';
}
}
memset(visited,0,sizeof(visited));
// cout<<"ReadInput is over!"<<endl;
}
void goOn(Box V){
// cout<<"start to goOn"<<endl;
if(V.r+1<=n && G[V.r+1][V.c]==0 && visited[V.r+1][V.c]==0 ){ //检测下方 是否有路
visited[V.r+1][V.c]=1;
GG[V.r+1][V.c].r =V.r+1;
GG[V.r+1][V.c].c=V.c;
GG[V.r+1][V.c].fr=V.r;
GG[V.r+1][V.c].fc=V.c;
GG[V.r+1][V.c].steps=V.steps+1;
Q.push( GG[V.r+1][V.c] );
}
if( V.c+1<=m && G[V.r][V.c+1]==0 && visited[V.r][V.c+1]==0 ){//检测右侧 是否有路
visited[V.r][V.c+1]=1;
GG[V.r][V.c+1].r =V.r;
GG[V.r][V.c+1].c=V.c+1;
GG[V.r][V.c+1].fr=V.r;
GG[V.r][V.c+1].fc=V.c;
GG[V.r][V.c+1].steps=V.steps+1;
Q.push( GG[V.r][V.c+1] );
}
if( V.r-1>=1 && G[V.r-1][V.c]==0 && visited[V.r-1][V.c]==0 ){//检测上方 是否有路
visited[V.r-1][V.c]=1;
GG[V.r-1][V.c].r =V.r-1;
GG[V.r-1][V.c].c=V.c;
GG[V.r-1][V.c].fr=V.r;
GG[V.r-1][V.c].fc=V.c;
GG[V.r-1][V.c].steps=V.steps+1;
Q.push( GG[V.r-1][V.c] );
}
if( V.c-1>=1 && G[V.r][V.c-1]==0 && visited[V.r][V.c-1]==0 ){//检测左侧 是否有路
visited[V.r][V.c-1]=1;
GG[V.r][V.c-1].r =V.r;
GG[V.r][V.c-1].c=V.c-1;
GG[V.r][V.c-1].fr=V.r;
GG[V.r][V.c-1].fc=V.c;
GG[V.r][V.c-1].steps=V.steps+1;
Q.push( GG[V.r][V.c-1] );
}
// cout<<"goOn is over"<<endl;
}
Box BFS(Box S){
// cout<<"start to BFS"<<endl;
visited[S.r][S.c]=1;
Q.push(S);
while(!Q.empty()){
Box V=Q.front();
Q.pop();
if(V.r==n && V.c==m){
return V;
}
goOn(V);
}
}
char findDir(Box B){
//找出当前节点 与 父节点 的位置关系
if(B.r==B.fr-1 && B.c==B.fc ){//在父节点上方
return 'U';
}
if( B.r==B.fr+1 && B.c==B.fc ){ //在父节点下方
return 'D';
}
if( B.r==B.fr && B.c==B.fc-1 ){ //在父节点左侧
return 'L';
}
if( B.r==B.fr && B.c==B.fc+1 ){ //在父节点右侧
return 'R';
}
}
int main(int argc, char** argv) {
ReadInput();
GG[1][1].r=GG[1][1].c=1;
GG[1][1].steps=0;
Box final=BFS(GG[1][1]);
cout<<final.steps<<endl;
stack<char> Dir;
Box tmp=final;
while( 1 ){
Dir.push( findDir(tmp) );
tmp=GG[tmp.fr][tmp.fc];
// cout<<"stack push"<<endl;
if(tmp.r==1 && tmp.c==1){
break;
}
}
while(!Dir.empty()){
char C=Dir.top();
cout<<C;
Dir.pop();
}
return 0;
}