题目链接:http://poj.org/problem?
id=3984
这个本来是个模板题,可是老师要去不能用STL里的queue,得自己手写解决。ORZ....看别人的博客学习。新技能get。。。
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std;
int Map[10][10];
int last=0,total=1; // total为队列总元素,last为先驱标记。
int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
struct node
{
int x,y,pre;
}q[30];
bool Isok(int x,int y) // 推断时候在迷宫内部。决定时候继续往下搜;
{
if(x<0||y<0||x>4||y>4||Map[x][y]) return false;
else return 1;
}
void print(int i) // 自己定义输出函数,调用递归,利用递归原理能够非常轻松的从后往前输出。
{
if(q[i].pre!=-1){ // 先驱为-1位起点;
print(q[i].pre);
printf("(%d, %d)\n",q[i].x,q[i].y);
}
}
void bfs(int x,int y)
{
q[last].x=x;
q[last].y=y;
q[last].pre=-1; // 起点,先驱标记为-1;
while(last<total){ // 推断队列是否为空;
for(int i=0;i<4;i++){ // 四个方向搜索。
int a=q[last].x+dir[i][0];
int b=q[last].y+dir[i][1];
if(Isok(a,b)){
//cout<<a<<' '<<b<<endl;
Map[a][b]=1;
q[total].x=a;
q[total].y=b;
q[total].pre=last; // 记录先驱;
total++; // 入队;
}
if(a==4&&b==4){
print(last);
}
}
last++; // 出队。
}
}
int main()
{
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
scanf("%d",&Map[i][j]);
}
}
printf("(0, 0)\n");
bfs(0,0);
printf("(4, 4)\n");
return 0;
}