首页 > 代码库 > 挑战程序2.1.4 穷竭搜索>>深度优先搜索 练习题 POJ1979黑与红

挑战程序2.1.4 穷竭搜索>>深度优先搜索 练习题 POJ1979黑与红

http://poj.org/problem?id=1979

Description

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can‘t move on red tiles, he can move only on black tiles. 

Write a program to count the number of black tiles which he can reach by repeating the moves described above. 

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20. 

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows. 

‘.‘ - a black tile 
‘#‘ - a red tile 
‘@‘ - a man on a black tile(appears exactly once in a data set) 
The end of the input is indicated by a line consisting of two zeros. 

Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).
思路:(⊙v⊙)嗯和例题同理啊,从@开始,搜索到所有可以走到的地方,把那里改为一个值(@或者真值什么的),最后遍历一遍地图就好了。
 1 #include <stdio.h>
 2 char ch[24][24];
 3 void solve(int H,int W);
 4 void find1(int H,int W);
 5 void dfs(int x,int y,int H,int W);
 6 int main()
 7 {
 8     int H,W,i;
 9     while(scanf("%d%d",&W,&H)!=EOF&&H!=0&&W!=0)
10     {
11         getchar();
12      for(i=0;i<H;i++)
13         gets(ch[i]);
14      find1(H,W);
15      solve(H,W);
16     }
17     return 0;
18 }
19 
20 void solve(int H,int W)
21 {
22     int a=0;
23     for(int i=0;i<H;i++)
24         for(int k=0;k<W;k++)
25             if(ch[i][k]==@)
26                 a++;
27      printf("%d\n",a);
28 }
29 
30 void find1(int H,int W)
31 {
32     for(int i=0;i<H;i++)
33         for(int k=0;k<W;k++)
34             if(ch[i][k]==@)
35                 {
36                     dfs(i,k,H,W);
37                     return;
38                 }
39 }
40 
41 void dfs(int x,int y,int H,int W)
42 {
43     int x1,y1,nx,ny;
44     ch[x][y]=@;
45     for(x1=-1;x1<=1;x1++)
46     {
47         nx=x+x1;
48             if(nx>=0&&nx<H&&ch[nx][y]!=#&&ch[nx][y]!=@)
49                 dfs(nx,y,H,W);
50     }
51     for(y1=-1;y1<=1;y1++)
52     {
53         ny=y+y1;
54             if(ny>=0&&ny<W&&ch[x][ny]!=#&&ch[x][ny]!=@)
55                 dfs(x,ny,H,W);
56     }
57     return;
58 }

挑战程序2.1.4 穷竭搜索>>深度优先搜索 练习题 POJ1979黑与红