题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1312
问题描述
有一个长方形的房间，覆盖着正方形的瓷砖。每个磁贴都被着色为红色或黑色。一个人站在黑色的瓷砖上。他可以从一个图块移动到四个相邻图块之一。但是他不能在红色瓷砖上移动，只能在黑色瓷砖上移动。编写一个程序，通过重复上述动作来计算他可以到达的黑色瓷砖的数量。输入值 输入包含多个数据集。数据集从包含两个正整数W和H的行开始；W和H分别是x和y方向上的图块数。W和H不超过20。
数据集中还有H行，每行包括W个字符。每个字符表示瓦片的颜色，如下所示。
'。' -黑色图块
'＃'-红色图块
'@'-黑色图块上的一个人（在数据集中仅出现一次）
输出量 对于每个数据集，您的程序应输出一行，其中包含他可以从初始磁贴（包括其自身）达到的磁贴数量。
Sample Input 6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 11 9 .#......... .#.#######. .#.#.....#. .#.#.###.#. .#.#..@#.#. .#.#####.#. .#.......#. .#########. ........... 11 6 ..#..#..#.. ..#..#..#.. ..#..#..### ..#..#..#@. ..#..#..#.. ..#..#..#.. 7 7 ..#.#.. ..#.#.. ###.### ...@... ###.### ..#.#.. ..#.#.. 0 0
Sample Output 45 59 6 13
1 /*
2 * @Descripttion:
3 * @version:
4 * @Author: ZKYAAA
5 * @Date: 2020-04-15 09:54:01
6 * @LastEditors: 请叫我ZK谕啊啊啊
7 * @LastEditTime: 2020-04-15 12:37:06
8 */
9
10 //能AC代码
11 #include <bits/stdc++.h>
12 using namespace std;
13 int n,m,vis[30][30],sum,nx,ny;
14 int fx[4]={0,0,1,-1},fy[4]={1,-1,0,0};
15 char tile[30][30];
16 bool isp(int x,int y){
17 return nx>=0&&nx<n&&ny>=0&&ny<m;
18 }
19 void dfs(int x,int y){
20 sum++;
21 vis[x][y]=1;
22 for(int i=0;i<4;i++){
23 nx=x+fx[i];
24 ny=y+fy[i];
25 if(isp(nx,ny)&&!vis[nx][ny]&&tile[nx][ny]=='.')
26 dfs(nx,ny);
27 }
28 }
29
30 int main(){
31 while(cin>>m>>n,m!=0,n!=0){
32 sum=0;
33 memset(vis,0,sizeof(vis));
34 for(int i=0;i<n;i++)
35 cin>>tile[i];
36 for(int i=0;i<n;i++){
37 for(int j=0;j<m;j++){
38 if(tile[i][j]=='@'&&!vis[i][j]){
39 dfs(i,j);
40 break;
41 }
42 }
43 }
44 cout<<sum<<endl;
45 }
46 return 0;
47 }
48
49
50 //WA代码
51 #include <bits/stdc++.h>
52 using namespace std;
53 int wx,hy,sum;
54 const int MAXN=25;
55 char a[MAXN][MAXN];
56 int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
57 bool isp(int x,int y){
58 return x<wx&&x>=0&&y<hy&&y>=0;
59 }
60
61 struct node{int x,y;};
62
63 void bfs(int dx,int dy){
64 sum=1;
65 queue<node> q;
66 node start,next;
67 start.x=dx;
68 start.y=dy;
69 q.push(start);
70 while(!q.empty()){
71 start=q.front();
72 q.pop();
73 for(int i=0;i<4;i++){
74 next.x=start.x+dir[i][0];
75 next.y=start.y+dir[i][1];
76 if(isp(next.x,next.y)&&a[next.x][next.y]=='.'){
77 sum++;
78 a[next.x][next.y]='#';
79 q.push(next);
80 }
81 }
82 }
83 }
84
85 int main(){
86 int x,y,dx,dy;
87 while(cin>>wx>>hy){
88 if(wx==0&&hy==0)
89 break;
90 for(y=0;y<hy;y++){
91 for(x=0;x<wx;x++){
92 cin>>a[x][y];
93 if(a[x][y]='@'){
94 dx=x;
95 dy=y;
96 }
97 }
98 }
99 sum=0;
100 a[dx][dy]='#';
101 bfs(dx,dy);
102 cout<<sum<<endl;
103 }
104 return 0;
105 }
106
107 //AC代码
108 #include<bits/stdc++.h>
109 using namespace std;
110 const int MAXN=25;
111 char a[MAXN][MAXN];
112 int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
113 int wx,hy,sum;
114
115 bool isp(int x,int y){
116 return x<wx&&x>=0&&y<hy&&y>=0;
117 }
118
119 struct node
120 {
121 int x,y;
122 };
123 void bfs(int dx,int dy)
124 {
125 queue<node> q;
126 node start,next;
127 start.x = dx;
128 start.y = dy;
129 q.push(start);
130 while(!q.empty())
131 {
132 start = q.front();
133 q.pop();
134 for(int i=0;i<4;++i)
135 {
136 next.x=start.x+dir[i][0];
137 next.y=start.y+dir[i][1];
138 if(isp(next.x,next.y)&&a[next.x][next.y]=='.')
139 {
140 a[next.x][next.y]='#'; //标记已经走过
141 sum++;
142 q.push(next);
143 }
144 }
145 }
146 }
147 int main()
148 {
149 int x,y,dx,dy;
150
151 while(cin>>wx>>hy)
152 {
153 if(wx==0&&hy==0)
154 {
155 break;
156 }
157 for(y=0;y<hy;++y)
158 {
159 for(x=0;x<wx;++x)
160 {
161 cin>>a[x][y];
162 if(a[x][y]=='@')
163 {
164 dx=x;
165 dy=y;
166 }
167 }
168 }
169
170 sum=1;
171 bfs(dx,dy); //起点位置(dx,dy)
172 cout<<sum<<endl;
173 }
174 return 0;
175 }