問(wèn)題:
http://poj.org/problem?id=3051思路:
還是教科書(shū)式的DFS典型應(yīng)用，簡(jiǎn)單題
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_W 83
5 #define MAX_H 1001
6 #define is_valid(x,y) (x>=0 && x<H && y>=0 && y<W)
7 const int dx[] = {-1, 1, 0, 0};
8 const int dy[] = {0, 0, -1, 1};
9 char photo[MAX_H][MAX_W];
10 int hash[MAX_H][MAX_W];
11 int W, H;
12
13 int
14 dfs(int x, int y)
15 {
16 int i, nx, ny, rt = 1;
17 hash[x][y] = 1;
18 for(i=0; i<4; i++) {
19 nx = x+dx[i];
20 ny = y+dy[i];
21 if(is_valid(nx, ny) && photo[nx][ny]=='*' && !hash[nx][ny])
22 rt += dfs(nx, ny);
23 }
24 return rt;
25 }
26
27 int
28 solve()
29 {
30 int i, j, tmp, value = -1;
31 for(i=0; i<H; i++)
32 for(j=0; j<W; j++) {
33 if(photo[i][j]=='*' && !hash[i][j]) {
34 tmp = dfs(i, j);
35 value = tmp > value ? tmp : value;
36 }
37 }
38 return value;
39 }
40
41 int
42 main(int argc, char **argv)
43 {
44 int i;
45 while(scanf("%d %d", &W, &H) != EOF) {
46 for(i=0; i<H; i++)
47 scanf("%s", photo[i]);
48 memset(hash, 0, sizeof(hash));
49 printf("%d\n", solve());
50 }
51 }