poj3984迷宫问题(DFS广搜)
2024-10-01 06:12:39
迷宫问题
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;
}
最新文章
- Web性能优化:基本思路和常用工具
- UnicodeDecodeError: ‘XXX&#39; codec can&#39;t decode bytes in position X 的问题
- 微信支付官方.net版之坑你没商量
- extjs 选项卡
- eclipse 智能提示
- 【Python】Python-用大写字母打印你的名字
- ObjectQuery查询及方法
- windows下RabbitMQ 监控
- SharePoint2013基于Form(FBA)的AD认证登陆
- php封装+租房子练习题
- jquery选中radio或checkbox的正确姿势
- 翻译:SET NAMES
- java实现开根号算法
- Spring Cloud 2-Eureka服务发现注册(一)
- appium+python测试app使用相对坐标定位元素
- PHP 抽象类
- java虚拟机学习
- 几个linux内核参数
- Beta阶段——第6篇 Scrum 冲刺博客
- 64位系统VBS调用32位COM组件
热门文章
- EF Core 相关的千倍性能之差: AutoMapper ProjectTo VS Mapster ProjectToType
- masonry布局说明
- API认证&;SDK&;RESTful
- WinAPI 字符及字符串函数(15): CharNext、CharPrev
- mysql GROUP_CONCAT 查询某个字段(查询结果默认逗号拼接)
- 框架及其技术(Android)
- 【Vagrant】-NO.130.Vagrant.1 -【Vagrant】
- Redis和mysql数据怎么保持数据一致的?
- 团队项目第一篇——NABCD
- Go 初体验 - 常量 与 iota