【HDOJ】2531 Catch him

简单BFS。就是要把所有的D点当成一个整体考虑（整体移动）。
 1 /* 2531 */
 2 #include <iostream>
 3 #include <queue>
 4 #include <cstdio>
 5 #include <cstring>
 6 #include <cstdlib>
 7 using namespace std;
 8 
 9 #define MAXN 105
10 
11 typedef struct {
12     int x[21], y[21];
13     int t;
14 } node_t;
15 
16 int dn, n, m;
17 int visit[MAXN][MAXN];
18 char map[MAXN][MAXN];
19 node_t beg;
20 int dir[4][2] = {
21     -1,0,1,0,0,-1,0,1
22 };
23 
24 inline bool check(int x, int y) {
25     return x<0 || x>=n || y<0 || y>=m;
26 }
27 
28 int bfs() {
29     int i, j, k;
30     node_t nd, tmp;
31     queue<node_t> Q;
32     bool flag, catchQ;
33     
34     memset(visit, 0x3f, sizeof(visit));
35     visit[beg.x[0]][beg.y[0]] = beg.t;
36     Q.push(beg);
37     
38     while (!Q.empty()) {
39         nd = Q.front();
40         Q.pop();
41         tmp.t = nd.t + 1;
42         for (i=0; i<4; ++i) {
43             flag = true;
44             catchQ = false;
45             for (j=0; j<dn; ++j) {
46                 tmp.x[j] = nd.x[j] + dir[i][0];
47                 tmp.y[j] = nd.y[j] + dir[i][1];
48                 if (check(tmp.x[j], tmp.y[j]) || map[tmp.x[j]][tmp.y[j]]=='O') {
49                     flag = false;
50                     break;
51                 }
52                 if (map[tmp.x[j]][tmp.y[j]] == 'Q') {
53                     catchQ = true;
54                 }
55             }
56             if (flag) {
57                 if (catchQ)
58                     return tmp.t;
59                 if (visit[tmp.x[0]][tmp.y[0]] > tmp.t) {
60                     visit[tmp.x[0]][tmp.y[0]] = tmp.t;
61                     Q.push(tmp);
62                 }
63             }
64         }
65     }
66     
67     return -1;
68 }
69 
70 int main() {
71     int i, j, k;
72     
73     #ifndef ONLINE_JUDGE
74         freopen("data.in", "r", stdin);
75         freopen("data.out", "w", stdout);
76     #endif
77     
78     beg.t = 0;
79     while (scanf("%d%d",&n,&m)!=EOF && (n||m)) {
80         dn = 0;
81         for (i=0; i<n; ++i) {
82             scanf("%s", map[i]);
83             for (j=0; j<m; ++j) {
84                 if (map[i][j] == 'D') {
85                     beg.x[dn] = i;
86                     beg.y[dn] = j;
87                     ++dn;
88                 }
89             }
90         }
91         k = bfs();
92         if (k < 0)
93             puts("Impossible");
94         else
95             printf("%d
", k);
96     }
97     
98     return 0;
99 }