Red and Black HDU - 1312

题目

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)
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).
Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

Sample Output

1
2
3
4
45
59
6
13

思路

dfs简单应用。
从起点出发,搜索上下左右可走的位置。当找到位置后,又以该元素为起点来搜索。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<string>
using namespace std;
const int MAXSIZE=20+4;
string str[MAXSIZE];
int ans=0;
int N,M;
void DFS(int x,int y){
ans++;
str[x][y]='#';
//cout<<x<<' '<<y<<endl;
for(int i=x-1;i<=x+1;i++){
if(i>=0&&i<M&&str[i][y]=='.')
DFS(i,y);
}
for(int j=y-1;j<=y+1;j++)
if(j>=0&&j<N&&str[x][j]=='.')
DFS(x,j);
}
int main(){
while(cin>>N>>M){
if(N==0&&M==0) break;
ans=0;
int startX=0;
int startY=0;
for(int i=0;i<M;i++)
for(int j=0;j<N;j++){
cin>>str[i][j];
if(str[i][j]=='@'){
startX=i;
startY=j;
}
}
DFS(startX,startY);
cout<<ans<<endl;
// cout<<startX<<' '<<startY<<endl;
}
return 0;
}
-------------本文结束感谢您的阅读-------------
0%