题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1312
Red and Black
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 17773 Accepted Submission(s):
10826
Problem 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.
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.
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).
which contains the number of tiles he can reach from the initial tile (including
itself).
Sample Input
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0
Sample Output
45
59
6
13
题目大意： “.”代表黑地板，“#”代表红地板，“@”代表人的位置，人可以经过黑地板不能经过红地板，问在给定的图中人一共可以经过多少块地板
解题思路：深搜，在每个位置都搜索该位置的上下左右四个位置，将图中能够经过的点全部搜一遍
AC代码：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
int w,h;
int a[][] = {{-,},{,},{,-},{,}}; //位置数组
char str[][];
int f[][]; //标记该位置是否走过
int sum;
void dfs(int x,int y)
{
f[x][y] = ;
for (int i = ; i < ; i ++)
{
int x1=x + a[i][];
int y1=y + a[i][];
if (x1 >= && x1 < h && y1 >= && y1 < w && str[x1][y1]!='#' && f[x1][y1] == )
{ //判断边界、是否是不能经过的红地板、该地板是否已经经过
sum ++;
dfs(x1,y1);
}
}
}
int main ()
{
int i,j,x,y;
while (scanf("%d%d",&w,&h),w&&h)
{
for (i = ; i < h; i ++)
scanf("%s",str[i]); memset(f,,sizeof(f));
for (i = ; i < h; i ++)
for (j = ; j < w; j ++)
if (str[i][j] == '@') //找出人的位置
{
x = i;
y = j;
break;
}
sum = ;
dfs(x,y);
printf("%d\n",sum);
}
return ;
}