1216：红与黑
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。
【输入】
包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下:
1）‘.’：黑色的瓷砖；
2）‘#’：白色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时，表示输入结束。
【输出】
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
【输入样例】
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
【输出样例】
45
【来源】
No
1. //深搜 注意越界问题 2. #include<bits/stdc++.h> 3. using namespace std; 4. char c; 5. int w,h,x,y,sum; 6. int s[25][25]={0}; 7. int dfs(int a,int b) 8. { 9. sum++; 10. s[a][b]=0; 11. if(s[a-1][b]) dfs(a-1,b); 12. if(s[a][b+1]) dfs(a,b+1); 13. if(s[a+1][b]) dfs(a+1,b); 14. if(s[a][b-1]) dfs(a,b-1); 15. } 16. int main() 17. { 18. while((cin>>w>>h)&&!(w==0&&h==0)){ 19. sum=0; 20. memset(s,0,sizeof(s)); 21. for(int i=1;i<=h;i++) 22. for(int j=1;j<=w;j++){ 23. cin>>c; 24. if(c=='.'||c=='@') s[i][j]=1; 25. if(c=='@') { 26. x=i; 27. y=j; 28. } 29. } 30. dfs(x,y); 31. cout<<sum<<endl; 32. } 33. return 0; 34. }
1. //广搜 2. #include<iostream> 3. #include<cstdio> 4. #include<cstring> 5. using namespace std; 6. int dx[4]={0,1,0,-1}; 7. int dy[4]={-1,0,1,0}; 8. int s[1001][1001]; 9. int sum,m,n; 10. void gsy(int a,int b) 11. { 12. int x,y,t,w,i; 13. int h[1001][3]; 14. s[a][b]=0; 15. sum=1; 16. t=0; 17. w=1; 18. h[1][1]=a; 19. h[1][2]=b; 20. do{ 21. t++; 22. for(i=0;i<4;i++){ 23. x=h[t][1]+dx[i]; 24. y=h[t][2]+dy[i]; 25. if((x>0)&&(x<=n)&&(y>0)&&(y<=m)&&(s[x][y]==1)){ 26. w++; 27. sum++; 28. h[w][1]=x; 29. h[w][2]=y; 30. s[x][y]=0; 31. } 32. } 33. }while(t<w); 34. cout<<sum<<endl; 35. } 36. 37. int main() 38. { 39. char c; 40. int i,j,xx,yy; 41. while((cin>>m>>n)&&!(m==0&&n==0)){ 42. memset(s,0,sizeof(s)); 43. sum=0; 44. for(int i=1;i<=n;i++) 45. for(int j=1;j<=m;j++){ 46. cin>>c; 47. if(c=='.'||c=='@') s[i][j]=1; 48. if(c=='@') { 49. xx=i; 50. yy=j; 51. } 52. } 53. gsy(xx,yy); 54. } 55. return 0; 56. }
