#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
#include <stack>
using namespace std;
int dir[]={-1,0,1,0};
int dil[]={0,-1,0,1};
int num[6][6];
int visit[6][6];
int d[30];
struct node
{
int x,y,id;
}a[30];
int cet;
void bfs()
{
queue<node>q;
cet = 0;
a[cet].x = 0;
a[cet].y = 0;
a[cet].id = 0;
d[0]=-1;
q.push(a[cet]);
bool flag = true;
while(!q.empty()&&flag)
{
node xx = q.front();
int t = xx.id;
q.pop();
visit[xx.x][xx.y] = true;
for(int k=0;k<=3;k++)
{
int p = xx.x+dir[k];
int v = xx.y+dil[k];
if(!visit[p][v]&&num[p][v]!=1&&p>=0&&p<5&&v>=0&&v<5)
{
cet++;
d[cet] = t;
a[cet].x = p;
a[cet].y = v;
a[cet].id = cet;
q.push(a[cet]);
if(a[cet].x==4&&a[cet].y==4)
{
flag = false;
break;
}
}
}
}
}
int main()
{
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
scanf("%d",&num[i][j]);
visit[i][j] = false;
}
}
memset(d,-1,sizeof(d));
bfs();
stack<node>st;
while(cet>=0)
{
st.push(a[cet]);
cet=d[cet];
}
while(!st.empty())
{
node ll = st.top();
printf("(%d, %d)\n",ll.x,ll.y);
st.pop();
}
return 0;
}
分享到:
相关推荐
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
poj 800+ 题目源代码,多年做题积累 包含各种类型经典题目
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
SPOJ3 AC程序 BF SPOJ3 AC程序 BF SPOJ3 AC程序 BF
很好很强大的POJ分类 新手+进阶+题目完全分类 赶快下载
西北工业大学POJ试题C++答案代码+课程设计
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ初级-简单搜索 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1750462
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
POJ 3131 双向BFS解立体八数码问题
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
POJ1837-Balance 解题报告+AC代码
北大POJ2503-Babelfish 解题报告+AC代码