POJ 3984 迷宫问题(BFS:迷宫最短路径且输出路径)
http://poj.org/problem?id=3984
分析:
典型的BFS应用,要你求从左上角到右下角的最短路径,且保证有唯一解,且要输出路径.
直接BFS求解即可,需要用到vis数组和dist数组,用pre数组来保存当前节点的最短路径上的前一个点(或方向也行).
其实也可以不用pre数组的,可以直接倒推出最短路径.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
int maze[10][10];
int vis[10][10],dist[10][10];
int dr[]={-1,1,0,0};//上,下,左,右
int dc[]={0,0,-1,1};
struct Node
{
int r,c;//也可以在Node中加一个int pre属性,然后做一个全局的nodes,就不用pre[][]数组了.
Node(int r,int c):r(r),c(c){}
Node(){}
}pre[10][10];
queue<Node> Q;
void BFS()
{
while(!Q.empty()) Q.pop();
memset(vis,0,sizeof(vis));
dist[0][0]=0;
vis[0][0]=1;
Q.push(Node(0,0));
while(!Q.empty())
{
Node node=Q.front();Q.pop();
int r=node.r,c=node.c;
for(int d=0;d<4;d++)
{
int nr=r+dr[d];
int nc=c+dc[d];
if(nr>=0&&nr<5&&nc>=0&&nc<5&&vis[nr][nc]==0&&maze[nr][nc]==0)
{
vis[nr][nc]=1;
Q.push(Node(nr,nc));
dist[nr][nc]=1+dist[r][c];
pre[nr][nc]=Node(r,c);
if(nr==4&&nc==4) return ;
}
}
}
}
int main()
{
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
scanf("%d",&maze[i][j]);
BFS();
stack<Node> S;
int cur_r=4,cur_c=4;
while(true)
{
S.push(Node(cur_r,cur_c));
if(cur_r==0&&cur_c==0) break;
int r=cur_r,c=cur_c;
cur_r=pre[r][c].r;
cur_c=pre[r][c].c;
}
while(!S.empty())
{
Node node=S.top(); S.pop();
printf("(%d, %d)\n",node.r,node.c);
}
return 0;
}
分享到:
相关推荐
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
算法入门—广度优先搜索—raphealguo
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练)
poj 1062 昂贵的聘礼 代码 单源最短路径的Dijkstra算法
POJ 1300 Door Man:无向图、欧拉定理、gets、sscanf
POJ上的DP分类: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵,求...
北大POJ初级题-数据结构:解题报告+AC代码
想看看自己的编程能力到底怎么样,很多人都回去做一做POJ的题目吧,在这里你不妨可以先看看它的题目分析。
poj还是leetcode ProgrammingCompetionCareer 大学的竞赛生涯结束了,抽时间整理了一部分曾经在OJ刷过的题,还有一些找不到了,或者是因为杂物太多(除了代码以外还有题解的pdf、题目的测试数据等等),不想整理了就...
POJ1321棋盘问题 很好两种解法很值得去参考一下 完整的实验报告还有代码希望kan
poj 2820 古代密码 http://poj.grids.cn/problem?id=2820 可直接运行
poj1125原创AC代码,用的是folyd算法,求出所有点之间的最短路径,再以此求出每个点到其他点的最长路径。。。
poj1002 source code input: The input will consist of one case. The first line of the input specifies the number of telephone numbers in the directory (up to 100,000) as a positive integer alone on ...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
网上整理的一些poj刷题指南。 poj地址:http://poj.org
放炮问题,北大网站 POJ 1185 算法
poj与leetcode
poj 5346题,四则运算表达式求值的实现,用栈和队列实现中缀转后缀后计算,含解题报告与源码
poj1691解题报告 题目来源:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691) 解法: 搜索