POJ 1979 Red and Black

Red and Black

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 44452		Accepted: 24070

• 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.

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)
The end of the input is indicated by a line consisting of two zeros.

• 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

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#[email protected]#.#.
.#.#####.#.
.#.......#.
.#########.
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
[email protected]
###.###
..#.#..
..#.#..
0 0

• Sample Output

45
59
6
13

• Source

Japan 2004 Domestic

• Tips

DFS深搜 如果能前进继续搜索ans+1，不能的话return.

注意数组下标第一个是y，第二个是x. 和平常不同.

• Answer:

https://paste.ubuntu.com/p/6hkNM7cR7C/

#include<cstdio>
#define SIZE 21
using namespace std;
void bfs(int i, int j);
char in[SIZE][SIZE];
int W, H;

int res = 1;
int main(void)
{
	int i, j;
	//读取

	scanf("%d %d", &W, &H);
	
	while(W != 0 && H!= 0){
	
	for(int n = 0; n < H; n++){
		scanf("%s", in[n]);
	}
	//搜索起点 
	for(int n = 0; n < H; n++){
		for(int m = 0; m < W; m++){
			if(in[n][m] == '@') { // n~y; m~x
				i = n;
				j = m;
			}
		}
	}
	//处理
	bfs(i,j); 
	printf("%d\n", res); 
	res = 1;
	scanf("%d %d", &W, &H);
	
    }
	return 0;
 } 
 
void bfs(int i, int j)
{
	
	in[i][j] = '#'; //将起点设置为走过了 
	
	int dx[] = {1, 0, -1, 0};
	int dy[] = {0, 1, 0, -1};

	for(int n = 0; n < 4; n++){//四个方向走 
		int ny = i + dy[n], nx = j + dx[n] ;
		if(ny >= 0 && ny < H && nx >= 0 && nx < W && in[ny][nx] != '#') // 可以走 
		{
			res++;
			bfs(ny, nx);	
		}	
	}
	return ;
	
}