http://poj.org/problem?id=3984
其实是将九度的1335重写了一遍，不过，不小心操作数组时越界了，在队列中没有任何元素时，用gdb调试时，提示有-127个元素，汗。。，然后没有别的什么大问题了。不过不知道为什么，今天写的代码思路很乱，也不再改了。
什么叫少了一个人。。。小雨啊。。
1 #include <stdio.h>
2 #include <queue>
3 #include <stack>
4 using namespace std;
5 int maze[7][7];
6 int degree[7][7];
7 typedef struct Father{
8 int x,y;
9 }Father;
10 Father father[7][7];
11 queue<int> Q;
12 stack<int> S;
13 int x_pos[]={0,0,-1,1};
14 int y_pos[]={-1,1,0,0};
15 void bfs()
16 {
17 while(!Q.empty()){
18 int x=Q.front();
19 Q.pop();
20 int y=Q.front();
21 Q.pop();
22 if(x==y&&y==5)
23 break;
24 int i;
25 degree[x][y]++;
26 for(i=0;i<4;i++){
27 if(!degree[x+x_pos[i]][y+y_pos[i]]&&
28 !maze[x+x_pos[i]][y+y_pos[i]]){
29 father[x+x_pos[i]][y+y_pos[i]].x=x;
30 father[x+x_pos[i]][y+y_pos[i]].y=y;
31 Q.push(x+x_pos[i]);
32 Q.push(y+y_pos[i]);
33 }
34 }
35 }
36 }
37 void output()
38 {
39 int i=5,j=5;
40 while(!(i==1&&j==1)){
41 S.push(j);
42 S.push(i);
43 int a,b;
44 a=father[i][j].x;
45 b=father[i][j].y;
46 i=a;
47 j=b;
48 }
49 printf("(0, 0)\n");
50 while(!S.empty()){
51 int x=S.top();
52 S.pop();
53 int y=S.top();
54 S.pop();
55 printf("(%d, %d)\n",x-1,y-1);
56 }
57 }
58
59 int main()
60 {
61 int i,j;
62 for(i=0;i<=6;i++)
63 for(j=0;j<=6;j++){
64 maze[i][j]=1;
65 degree[i][j]=0;
66 father[i][j].x=1;
67 father[i][j].y=1;
68 }
69 for(i=1;i<=5;i++)
70 for(j=1;j<=5;j++){
71 scanf("%d",&maze[i][j]);
72 }
73 Q.push(1);
74 Q.push(1);
75 bfs();
76 output();
77 }