1076 - 红与黑
小明站在一个矩形房间里，这个房间的地面铺满了地砖，每块地砖的颜色或是红色或是黑色。小明一开始站在一块黑色地砖上，并且小明从一块地砖可以向上下左右四个方向移动到其他的地砖上，但是他不能移动到红色地砖上，只能移动到黑色地砖上。
请你编程计算小明可以走到的黑色地砖最多有多少块。
Input
输入包含多组测试数据。
每组输入首先是两个正整数W和H，分别表示地砖的列行数。（1<=W,H<=20）
接下来H行，每行包含W个字符，字符含义如下：
‘.’表示黑地砖；
‘#’表示红地砖；
‘@’表示小明一开始站的位置，此位置是一块黑地砖，并且这个字符在每组输入中仅会出现一个。
当W=0，H=0时，输入结束。
Output
对于每组输入，输出小明可以走到的黑色地砖最多有多少块，包括小明最开始站的那块黑色地砖。
Examples
Input
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 11 9 .#......... .#.#######. .#.#.....#. .#.#.###.#. .#.#..@#.#. .#.#####.#. .#.......#. .#########. ........... 11 6 ..#..#..#.. ..#..#..#.. ..#..#..### ..#..#..#@. ..#..#..#.. ..#..#..#.. 7 7 ..#.#.. ..#.#.. ###.### ...@... ###.### ..#.#.. ..#.#.. 0 0
Output
45 59 6 13
Solution C
#include<stdio.h> int W, H; int count; int vis[30][30]; char str[30][30]; struct Point{ int x, y; }Start; int dx[]={-1,0,1,0}, dy[]={0,1,0,-1}; void Scan_Point();//输入函数 void DFS(struct Point p);//执行函数 int main() { while(scanf("%d%d",&H,&W)){ if(W==0 && H==0) break; count=1; Scan_Point(); DFS(Start); printf("%d\n",count); } return 0; } void Scan_Point(){ int i, j; getchar(); for(i=0; i<W; i++){ for(j=0; j<H; j++){ scanf("%c",&str[i][j]); vis[i][j]=1; if(str[i][j]=='@'){ Start.x=i; Start.y=j; } } getchar(); } } void DFS(struct Point p){ int a, b; int i, j; struct Point temp; for(i=0; i<4; i++){ a=p.x+dx[i]; b=p.y+dy[i]; temp.x=a; temp.y=b; if(a>=0 && a<W && b>=0 && b<H && str[a][b]=='.' && vis[a][b]){ count++; vis[a][b]=0; DFS(temp); } } return ; }
Solution C++
#include<iostream> #include<cstring> #include<queue> using namespace std; struct N { int x,y; }start,head,tail; char g[20][20]; int w,h,sum,v[20][20],f[][2]={{-1,0},{0,-1},{1,0},{0,1}}; int bfs() { sum=0; memset(v,0,sizeof(v)); v[start.x][start.y]=1; queue<struct N> q; q.push(start); while(!q.empty()) { sum++; head=q.front(); q.pop(); for(int i=0;i<4;i++) { tail.x=head.x+f[i][0]; tail.y=head.y+f[i][1]; if(!v[tail.x][tail.y]&&tail.x>=0&&tail.x<h&&tail.y>=0&&tail.y<w&&g[tail.x][tail.y]=='.') { q.push(tail); v[tail.x][tail.y]=1; } } } return sum; } int main() { int i,j; while(cin>>w>>h,w||h) { for(i=0;i<h;i++) for(j=0;j<w;j++) { cin>>g[i][j]; if(g[i][j]=='@') { start.x=i; start.y=j; } } cout<<bfs()<<endl; } return 0; }