算法提高 学霸的迷宫  
时间限制: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 <algorithm>
#include <cstdlib>
#include <utility>
#include <map>
#include <cstdio>
#include <queue>
using namespace std; const int maxn = + ;
const int INF = ;
typedef pair<int,int> P;
// D(下), L(左), R(右), U(上)
int dir[][] = { {, }, {, -}, {, }, {-, }};
char dir_c[] = {'D', 'L', 'R', 'U'};
int row, col; //行列
char maze[maxn][maxn]; //表示迷宫的字符串的数组
int d[maxn][maxn]; //到各个位置的最短距离的数组
string Min; //U,D,L,R
queue<P> que;
void input();
bool judge(int r, int c);
int BFS(); void input()
{
scanf("%d%d", &row, &col);
for (int i = ; i < row; i++) {
for (int j = ; j < col; j++) {
cin >> maze[i][j];
}
}
//所有位置初始化
for (int i = ; i < row; i++) {
for (int j = ; j < col; j++) {
d[i][j] = INF;
}
}
} bool judge(int r, int c)
{
return (r >= && r < row) && (c >= && c < col)
&& (maze[r][c] != ''); //可走
} int BFS()
{
//将起点假如队列, 并把这一地点的距离设置为 0
que.push(P(, ));
queue<string> path;
path.push(""); d[][] = ;
Min = ""; while (!que.empty())
{
P p = que.front(); que.pop();
string t = path.front(); path.pop(); if (p.first == row - && p.second == col - ) {
Min = t; //因为我的方向就是按照字典序 DLRU,所以这时候形成最短路线的路径就是按照字典序最小的路线!
break;
} for (int i = ; i < ; i++) {
//移动之后的位置为(nx,ny)
int nx = p.first + dir[i][], ny = p.second + dir[i][]; //可以走,且尚未访问(d[nv][ny]==INF
if (judge(nx, ny) && d[nx][ny] == INF) {
//加入到队列,并且到该位置的距离确定为到p的距离+1
que.push(P(nx, ny));
path.push(t + dir_c[i]); //这里数据结构组织的并不好,我应该一开始就把路径和位置组合成结构体,会更方便
d[nx][ny] = d[p.first][p.second] + ; //因为是的方向就是按照 DLRU字典序遍历,所以不需要有什么额外的判断,只需要和行走路线
maze[nx][ny] = ''; //一起出队,入队就可以了!
}
}
}
return d[row - ][col - ];
} void solve()
{
input();
int res = BFS();
printf("%d\n%s\n", res, Min.c_str());
} int main()
{
solve();
return ;
}

最新文章

  1. linux 调用java main方法
  2. java获取服务器IP地址及MAC地址的方法
  3. phpcms v9 的表单向导功能的使用方法
  4. Add two numbers [LeetCode]
  5. 使用busybox构建根文件系统
  6. linux下从源代码安装git
  7. nenu contest3 The 5th Zhejiang Provincial Collegiate Programming Contest
  8. Android应用程序框架之无边界设计意图
  9. Linux系统开机启动流程
  10. PHP. 01. C/S架构、B/S架构、服务器类型、服务器软件、HTTP协议/服务器、数据库、服务器web开发、PHP简介/常见语法、PHPheader()、 PHP_POST/GET数据获取和错误处理
  11. dmraid 用法
  12. oracle中数据类型对应java类型
  13. 值得收藏!!javascript数组中多条对象去重方式,很实用!!!
  14. HttpClient 测试web API上传文件实例
  15. C# chart 编程教程
  16. 【一】、搭建Hadoop环境----本地、伪分布式
  17. 【Java】HashTable和HashMap区别
  18. CSS3之border-image
  19. 基于TrueLicense实现产品License验证功能
  20. awk高级进阶

热门文章

  1. 程序开发入门工具之CodeBlocks
  2. Python开发【第五篇】迭代器、生成器、递归函数、二分法
  3. C++编译与链接(2)-浅谈内部链接与外部链接
  4. 30行js让你的rem弹性布局适配所有分辨率(含竖屏适配)(转载)
  5. 0422数学口袋精灵bug发现
  6. PAT 1067 试密码
  7. 利用css制作带边框的小三角
  8. cmd 中运行testng代码
  9. Excel作为数据源TesTNG做数据驱动完整代码
  10. Linux内核0.11 makefile文件说明