首页 > 代码库 > 挑战程序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.
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.
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黑与红
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。