迷宫问题

Time Limit: 1000MS
Memory Limit: 65536K

Description

定义一个二维数组:


int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径,格式如样例所示。

Sample Input

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
 
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
bool ism[5][5];
int a[5][5];
int dx[4]={0, 1, 0, -1};
int dy[4] = { 1, 0, -1, 0 };
struct Node{
int x;
int y;
int s;
short l[30];
};
bool judge(int x, int y){
if (x < 0 || x >= 5 || y < 0 || y >= 5)
return true;
if (ism[x][y])
return true;
if (a[x][y] == 1)
return true;
return false;
}
Node bfs(){
queue<Node> q;
Node cur, next;
cur.x = 0;
cur.y = 0;
cur.s = 0;
ism[cur.x][cur.y] = true;
q.push(cur);
while (!q.empty()){
cur = q.front();
q.pop();
if (cur.x == 4 && cur.y == 4)
return cur;
int i, nx, ny;
for (i = 0; i < 4; i++){
nx = cur.x + dx[i];
ny = cur.y + dy[i];
if (judge(nx, ny))
continue;
next = cur;
next.x = nx;
next.y = ny;
next.s = cur.s+1;
next.l[cur.s] = i;
q.push(next);
}
}
return cur;
}
int main(){
int i, j;
for (i = 0; i < 5; i++){
for (j = 0; j < 5; j++){
scanf("%d", &a[i][j]);
}
}
memset(ism, 0, sizeof(ism));
Node ans = bfs();
int x, y;
x = 0, y = 0;
for (i = 0; i<= ans.s; i++){
printf("(%d,%d)\n", x, y);
x += dx[ans.l[i]];
y += dy[ans.l[i]];
}
return 0;
}

最新文章

  1. Web性能优化:基本思路和常用工具
  2. UnicodeDecodeError: ‘XXX&#39; codec can&#39;t decode bytes in position X 的问题
  3. 微信支付官方.net版之坑你没商量
  4. extjs 选项卡
  5. eclipse 智能提示
  6. 【Python】Python-用大写字母打印你的名字
  7. ObjectQuery查询及方法
  8. windows下RabbitMQ 监控
  9. SharePoint2013基于Form(FBA)的AD认证登陆
  10. php封装+租房子练习题
  11. jquery选中radio或checkbox的正确姿势
  12. 翻译:SET NAMES
  13. java实现开根号算法
  14. Spring Cloud 2-Eureka服务发现注册(一)
  15. appium+python测试app使用相对坐标定位元素
  16. PHP 抽象类
  17. java虚拟机学习
  18. 几个linux内核参数
  19. Beta阶段——第6篇 Scrum 冲刺博客
  20. 64位系统VBS调用32位COM组件

热门文章

  1. EF Core 相关的千倍性能之差: AutoMapper ProjectTo VS Mapster ProjectToType
  2. masonry布局说明
  3. API认证&amp;SDK&amp;RESTful
  4. WinAPI 字符及字符串函数(15): CharNext、CharPrev
  5. mysql GROUP_CONCAT 查询某个字段(查询结果默认逗号拼接)
  6. 框架及其技术(Android)
  7. 【Vagrant】-NO.130.Vagrant.1 -【Vagrant】
  8. Redis和mysql数据怎么保持数据一致的?
  9. 团队项目第一篇——NABCD
  10. Go 初体验 - 常量 与 iota