问题描述
学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。
输入格式
第一行两个整数n， m，为迷宫的长宽。
接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。
接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。
输出格式
第一行一个数为需要的最少步数K。
第二行K个字符，每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。
第二行K个字符，每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。
样例输入
Input Sample 1:
3 3
001
100
110
Input Sample 2:
3 3
000
000
000
3 3
001
100
110
Input Sample 2:
3 3
000
000
000
样例输出
Output Sample 1:
4
RDRD
Output Sample 2:
4
DDRR
4
RDRD
Output Sample 2:
4
DDRR
数据规模和约定
有20%的数据满足：1<=n,m<=10
有50%的数据满足：1<=n,m<=50
在这里DFS我用的是非递归，个人觉得他的非递归思路更清晰，而且不会担心栈溢出，速度也会更快一些。很多题目必须用非递归，不然就会超时。
有50%的数据满足：1<=n,m<=50
有100%的数据满足：1<=n,m<=500
先用BFS得到最小路径矩阵，再用DFS以迷宫终点作为搜索起点（可以保证一定能得到完整路径），输出字典序最小的最短路径
在输出字典序最小的路径，我是将U,D,L,R排成 U R L D 这种顺序，然后在DFS中按此顺序移动，得到的第一个序列经过倒置和U<->D，R<->L的变换就是字典序最小的序列
比如Sample 1 DFS中移动得到的第一个序列是0 2 0 2 ，由于这是从终点作搜索起点的，所以得倒置，得到2 0 2 0
并将方向反向，得到 1 3 1 3，转换成字母则是 R D R D
下面是代码
#include<cstring>
#include<string>
#include<stdio.h>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 505
char maze[MAX][MAX];
int x[MAX][MAX];
int dr[] = { -1,0,0,1 };
int dc[] = { 0,1,-1,0 };
char dirs[] = { 'U','R','L','D' };
int r, c, minlen, numOfPath = 0;
string path;
string minPath;
vector<int> path_num;
class Cell
{
public:
int x;
int y;
int dir;
Cell() :x(x), y(y) {}
Cell(int x, int y) :x(x), y(y) {}
};
Cell walk(const Cell &c, int dir)
{
return Cell(c.x + dr[dir], c.y + dc[dir]);
}
bool is_inside(const Cell &cell)
{
return cell.x >= 0 && cell.x < r&&cell.y >= 0 && cell.y < c;
}
bool is_walk(const Cell &cell)
{
return maze[cell.x][cell.y] == '0'&&x[cell.x][cell.y] == -1;
}
bool is_arrive(const Cell &cell)
{
return cell.x == r - 1 && cell.y == c - 1;
}
void trans(vector<int> &s, string &str)
{
int size = s.size();
reverse(s.begin(), s.end());
for (int i = 0;i != size;++i)
{
s[i] = 3 - s[i];
str.push_back(dirs[s[i]]);
}
}
void print_path()
{
int len = minlen;
stack<Cell> s;
s.push(Cell(r - 1, c - 1));
while (!s.empty())
{
Cell cur = s.top();
if (cur.x != r - 1 || cur.y != c - 1)
path_num.push_back(cur.dir);
if (cur.x == 0 && cur.y == 0)
{
trans(path_num, path);
return;
}
s.pop();
for (int i = 0;i != 4;++i)
{
Cell next = walk(cur, i);
if (x[next.x][next.y] == len - 1)
{
next.dir = i;
s.push(next);
}
}
--len;
}
}
void bfs()
{
queue<Cell> q;
q.push(Cell(0, 0));
x[0][0] = 0;
while (!q.empty())
{
Cell cur = q.front();
if (is_arrive(cur))
{
minlen = x[cur.x][cur.y];
return;
}
q.pop();
for (int i = 0;i != 4;++i)
{
Cell next = walk(cur, i);
if (is_inside(next) && is_walk(next))
{
x[next.x][next.y] = x[cur.x][cur.y] + 1;
q.push(next);
}
}
}
}
int main()
{
/*scanf("%d%d", &r, &c);*/
cin >> r >> c;
memset(maze, '1', sizeof(maze));
memset(x, -1, sizeof(x));
for (int i = 0;i != r;++i)
{
cin >> maze[i];
/*scanf("%s", maze[i]);*/
}
bfs();
printf("%d\n", minlen);
print_path();
cout << path << "\n";
return 0;
}
在这里DFS我用的是非递归，个人觉得他的非递归思路更清晰，而且不会担心栈溢出，速度也会更快一些。很多题目必须用非递归，不然就会超时。