poj3984《迷宫问题》暑假集训-搜索进阶
Crawling in process... Crawling failed Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
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
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<algorithm>
#include<queue>
#include<string.h>
#include<stdio.h>
using namespace std;
int maps[5][5];
int dir[4][2]= {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
typedef struct maze
{
int x, y;
} MAZE;
MAZE s, n, p[5][5];//关键是定义了一个二维的结构体数组来存maps[i][j]处的前一个位置;
void Search(int a, int b);
void BFS();
int main()
{
int i, j;
for(i=0; i<5; i++)
for(j=0; j<5; j++)
cin >> maps[i][j];
s.x=0;
s.y=0;
//s=(MAZE){0, 0};
p[0][0]=(MAZE){-1, -1};
printf("(0, 0)\n");
BFS();
}
void BFS()
{
queue<MAZE>que;
que.push(s);
while(!que.empty())
{
s=que.front();
que.pop();
for(int i=0; i<4; i++)
{
n.x=s.x+dir[i][0];
n.y=s.y+dir[i][1];
if(n.x<5&&n.x>=0&&n.y<5&&n.y>=0&&maps[n.x][n.y]==0)
{
maps[n.x][n.y]=1;
p[n.x][n.y]=s;
que.push(n);
}
if(n.x==4&&n.y==4)
{
Search(4,4);
return;
}
}
}
}
void Search(int a, int b)
{
if(a==0&&b==0)
return ;
Search(p[a][b].x, p[a][b].y);
printf("(%d, %d)\n", a, b);
}
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
#define PI acos-1.0//
#define N 10
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
struct node
{
int x, y;
}s[N][N], sa;//定义的二维结构体数组;用处是判断
char g[N][N];
int vis[N][N];//防止重复搜索,这是我忘记的一点儿
void BFS (int x, int y);
void DFS (int x, int y);
int main ()
{
for (int i=0; i<5; i++)
{
for (int j=0; j<5; j++)
cin >> g[i][j];
getchar ();
}
sa = (node) {0, 0};//整体赋值,其实就相当于sa.x=0; sa.y=0;
s[1][1] = (node) {0, 0};//这里代表
BFS (0, 0);
DFS (4, 4);
printf ("(4, 4)\n");
}
void BFS (int x, int y)
{
memset (vis, 0, sizeof (vis));//vis数组代表是否进行广搜过
queue <node> que;
que.push (sa);
vis[sa.x][sa.y] = 1;
while (que.size())
{
sa = que.front(); que.pop();
for (int i=0; i<4; i++)
{
node q = sa;
q.x += dir[i][0], q.y += dir[i][1];
if (q.x>=0 && q.x<5 && q.y>=0 && q.y<5 && !vis[q.x][q.y] && g[q.x][q.y] == '0')
{
s[q.x][q.y] = (node) {sa.x, sa.y};//
vis[q.x][q.y] = 1;
que.push(q);
}
}
}
}
void DFS (int x, int y)
{
if (!x && !y)
return;
DFS (s[x][y].x, s[x][y].y);
printf ("(%d, %d)\n", s[x][y].x, s[x][y].y);
}
最新文章
- 【亚瑟士 ASICS 系列】
- [转载]SVN使用教程
- [原创]如何设计Lighthoused定位接收电路
- PureLayout和Masonry比较
- Android消息机制:Looper,MessageQueue,Message与handler
- 不重启使XP环境变量生效
- C# MySql分页存储过程的应用
- bzoj 1058 [ZJOI2007]报表统计(set)
- 【转】P2P之UDP穿透NAT的原理与实现(附源代码)
- .net 应用Memcached 缓存 demo(非转载,文件下载地址有效)
- 二叉堆 C++实现
- NYOJ--45--棋盘覆盖(大数)
- selenium--关键字驱动
- 第十篇:K均值聚类(KMeans)
- 201621123057 《Java程序设计》第7周学习总结
- Eclipse中Lombok的安装和注解说明
- 【一:定义】python 简介
- Android-Nexus5-命令刷机
- sparkStreaming序列化问题
- iOS开发之--在UIWindow上展示/移除一个View
热门文章
- mysql 主从切换
- 获取 Android 版本
- MySQL优化时可以设置的几个参数
- [原创]个人工具 - 对APK极限压缩并对齐的工具(58.ReExtremeZipAndAlignAPK)
- 快速搭建一个成熟,强壮的App框架【转载】
- [译]NeHe教程 - 你的第一个多边形
- linux模块导出符号 EXPORT_SYMBOL_GPL&;EXPORT_SYMBOL(转)
- IntelliJ idea——》删除tag
- js判断对象的属性是原型的还是实例的
- Java -- 数字