题目链接：http://poj.org/problem?id=1979

 

题目大意：

有一个长方形的房间，上面铺着正方形的瓷砖。每块瓷砖都是红色或黑色的。一个男人站在一块黑色的瓷砖上。从一个瓦片，他可以移动到四个相邻瓦片中的一个。但是他不能在红瓦上移动，他只能在黑瓦上移动。

 

编写一个程序，通过重复上面描述的动作来计算他可以到达的黑色方块的数量。

输入

输入由多个数据集组成。数据集以包含两个正整数W和H的行开始;W和H分别是x和y方向上的瓦片数。W和H不超过20。

'.——一块黑瓷砖

“#”——红色瓷砖

@——一个男人在黑色的平铺上(数据集中只出现一次）

 

思路：

找到起始位置然后进行 dfs，找到一个就标记一个，然后一直走下去

一开始自己想错了，我以为是找最多的可以走的。但是后来感觉根据题目的意思来看就是找到一条路就可以了。哭泣

 

AC代码：

 1 #include <cstdio>
 2 #include <string>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <string.h>
 6 #include <math.h>
 7 #include <vector>
 8 
 9 using namespace std;
10 
11 const int maxn = 30;
12 
13 char ss[maxn][maxn];
14 int mx[] = {0,0,1,-1};
15 int my[] = {1,-1,0,0};
16 int vis[maxn][maxn];
17 int n,m;
18 int cnt = 0;
19 
20 bool check(int i,int j)
21 {
22     if (ss[i][j] == '.' && !vis[i][j])
23         return true;
24     return false;
25 }
26 
27 void dfs(int row,int col)
28 {
29     for (int i=0;i<4;i++)
30     {
31         int nx = row + mx[i];
32         int ny = col + my[i];
33         if (check(nx,ny))
34         {
35             cnt++;
36             vis[nx][ny] = 1;
37             dfs(nx,ny);
38         }
39     }
40 
41 }
42 
43 
44 int main() {
45     while (cin >> m >> n) {
46         if (m == 0 && n == 0)
47             return 0;
48         bool flag = false;
49         cnt = 0;
50         memset(vis,0, sizeof(vis));
51         memset(ss,'#', sizeof(ss));
52         for (int i = 1; i <= n; i++) {
53             for (int j = 1; j <= m; j++) {
54                 cin >> ss[i][j];
55             }
56         }
57         for (int i = 1; i <= n; i++) {
58             for (int j = 1; j <= m; j++) {
59                 if (ss[i][j] == '@') {
60                     dfs(i, j);
61                     printf("%d\n", cnt + 1);
62                     flag = true;
63                     break;
64                 }
65             }
66             if (flag)
67                 break;
68         }
69     }
70 }