原题POJ3984：

http://poj.org/problem?id=3984

迷宫问题

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 13094		Accepted: 7853

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)

Source

嗯。这道题水到连出处都没有，正常来说我直接输出样例都能A，但做人要厚道~果断学习BFS
几个小时后，代码如下：

#include<cstdio>
#include<queue>
#include<iostream>
using namespace std;
int g[30];
bool m[30]={0};
int f[30];
void print(int x){
if (x){
print(f[x]);
}
printf("(%d, %d)n",x/5,x%5);
}
int main(){
int d[4]={1,-1,5,-5};
queue<int> q;
for (int i=0;i<25;i++) scanf("%d",&g[i]);
q.push(0);
f[0]=0;
m[0]=1;
while(!q.empty()){
int x,y,x2,y2;
int po;
po=q.front();
q.pop();
m[po]=1;
for (int i=0;i<4;i++){
int son;
son=po+d[i];

if(son<0||son>24) continue;
if(g[son]) continue;
x=son/5;
y=son%5;
x2=po/5;
y2=po%5;
if(x-x2>1||x-x2<-1||y-y2>1||y-y2<-1) continue;
if (!m[son]&&!g[son]&&y>=0&&y<5&&x>=0&&x<5)
{
q.push(son);
// cout<<"po:"<<po<<"son:"<<son;
f[son]=po;
}
}
}
print(24);
return 0;
}

AC。
允许我小小自满一下...