poj 3984

题目很简单，就是简单的BFS吧，主要的难点在于坐标的问题

这个呢，可以反其道而行之，就是你从（1，1）到（5,5），你肯定走过一次

走过一次呢，那么路径肯定也标记过，那么你完全就可以从(5，5)到（1,1）按标记的记号走一次，那样就是最短的路径了

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <queue>
 4 #include <string.h>
 5 
 6 using namespace std;
 7 
 8 queue<int>first;
 9 queue<int>second;
10 
11 int a[7][7],b[7][7],ans;
12 
13 
14 struct {        
15     int x,y;
16 }s[20];
17 
18 
19 bool mark[7][7]; 
20 
21 void bfs(int x,int y)
22 {
23    int he,ba;
24    first.push(x);
25    second.push(y);
26     while(!first.empty())
27     {
28         he=first.front();
29         first.pop();
30         ba=second.front();
31         second.pop();
32         //printf("%d %d
",he,ba);
33         if(he==5&&ba==5) break;
34         if(a[he][ba+1]==0&&mark[he][ba+1])
35             {
36                 first.push(he);
37                 second.push(ba+1);
38                 b[he][ba+1]=b[he][ba]+1;
39                 mark[he][ba+1]=false;
40             }
41         if(a[he+1][ba]==0&&mark[he+1][ba])
42         {
43             first.push(he+1);
44             second.push(ba);
45             b[he+1][ba]=b[he][ba]+1;
46             mark[he+1][ba]=false;
47         }
48     }
49 }
50 
51 void findroad(int x,int y)
52 {
53     if(x==1&&y==1) return;
54    if(!mark[x][y-1]){
55         ans--;
56         s[ans].x=x;
57         s[ans].y=y-1;
58         findroad(x,y-1);
59    }
60    if(!mark[x-1][y])
61    {
62        ans--;
63        s[ans].x=x-1;
64        s[ans].y=y;
65        findroad(x-1,y);
66    }
67 }
68 
69 int main()
70 {
71     memset(a,1,sizeof(a));
72     memset(mark,true,sizeof(mark));
73     memset(b,0,sizeof(b));
74     for(int i=1;i<=5;i++)
75         for(int j=1;j<=5;j++)
76             scanf("%d",&a[i][j]);
77     s[0].x=1;
78     s[0].y=1;
79     bfs(1,1);
80     ans=b[5][5];
81     s[ans].x=5;
82     s[ans].y=5;
83     findroad(5,5);
84     for(int i=0;i<=b[5][5];i++)
85         printf("(%d, %d)
",s[i].x-1,s[i].y-1);
86     return 0;
87 }