首页 > 代码库 > POJ1979 Red and Black

POJ1979 Red and Black

题目:POJ1979 Red and Black

思路:深度优先搜索

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int w[100000000];
 6 int h[100000000];
 7 int res[100000000];
 8 char tiles[20][20];
 9 
10 void dfs(int index, int x, int y) {
11     tiles[x][y] = #;
12     int dx[4] = {-1, 0, 1, 0};
13     int dy[4] = {0, -1, 0, 1};
14     for (int i = 0; i < 4; i++) {
15         int nx = x + dx[i];
16         int ny = y + dy[i];
17         if (nx >= 0 && ny >= 0 && nx < h[index] && ny < w[index] && tiles[nx][ny] == .) {
18             res[index]++;
19             dfs(index, nx, ny);
20         }
21     } 
22     return;
23 }
24 
25 void solve(int index) {
26     res[index] = 1;
27     for (int i = 0; i < h[index]; i++) {
28         for (int j = 0; j < w[index]; j++) {
29             if (tiles[i][j] == @) {
30                 dfs(index, i, j);
31             }
32         }
33     }
34 } 
35 int main() {
36     int index = 0;
37     do {
38         cin >> w[index] >> h[index];
39          for (int i = 0; i < h[index]; i++) {
40             for (int j = 0; j < w[index]; j++) {
41                cin >> tiles[i][j]; 
42            }
43         }
44         solve(index);
45         index++;
46     } 
47     while (w[index - 1] > 0 && h[index - 1] > 0);
48     
49     for (int i = 0; i < index -1; i++) {
50         cout << res[i] << endl;
51     }
52 
53     return 0;
54 } 

//第一个AC的OJ题目,加油

POJ1979 Red and Black