題目鏈接：http://poj.org/problem?id=1979 一九七九年啊，那是一個(gè)春天~~~~~ 這道題必須要把行列搞清楚了，否則的話，就像我似的，卡樣例卡了一宿。。。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 #include <queue>
8 using namespace std;
9 int map[25][25], G[25][25], w, h;
10 char s[25][25];
11 const int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
12 struct nod{
13 int x, y;
14 }S;
15 queue<nod> Q;
16 void init(){
17 memset(G, 0, sizeof(G));
18 memset(map, -1, sizeof(map));
19 for (int i = 0; i < h; i++)
20 for (int j = 0; j < w; j++){
21 if (s[i][j] == '.') G[i][j] = 0;
22 if (s[i][j] == '#') G[i][j] = 1;
23 if (s[i][j] == '@') {S.x = j; S.y = i;}
24 }
25 }
26 bool inMap(int x, int y){
27 return x >= 0 && x < w && y >= 0 && y < h;
28 }
29 void bfs(){
30 map[S.y][S.x] = 0;
31 Q.push(S);
32 while (!Q.empty()){
33 int x = Q.front().x;
34 int y = Q.front().y;
35 Q.pop();
36 for (int i = 0; i < 4; i++){
37 int xx = x + dir[i][0];
38 int yy = y + dir[i][1];
39 if (!inMap(xx, yy) || G[yy][xx] == 1) continue;
40 if (map[yy][xx] == -1 || map[y][x] + 1 < map[yy][xx]){
41 map[yy][xx] = map[y][x] + 1;
42 nod v; v.x = xx; v.y = yy;
43 Q.push(v);
44 }
45 }
46 }
47 }
48 int main(){
49 while (~scanf("%d%d", &w, &h)){
50 if (w == 0 && h == 0) break;
51 for (int i = 0; i < h; i++) scanf("%s", s[i]);
52 init();
53 bfs();
54 int ans = 0;
55 for (int i = 0; i < h; i++)
56 for (int j = 0; j < w; j++)
57 if (map[i][j] >= 0) ans += 1;
58 printf("%d\n", ans);
59 }
60 return 0;
61 }
62
|