poj 1979 Red and Black dfs

缘起

日常水题 poj 1979 Red and Black

分析

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
有一个矩形的屋子，铺满方形的瓷砖. 瓷砖不是红色就是黑色. 一个人站在黑色瓷砖上，他不能跑到红色瓷砖上。
所以他每一步只能移动4种方向（上下左右，不包括斜方向）. 写一个程序计算他能到达的黑色瓷砖个数.

【输入】
多样例. 每个样例以W和H两个整数开头，分别表示矩形屋子的宽和高 1<=W,H<=20
然后是一个W*H的字符矩阵.

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

【输出】
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).

【样例输入】
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

【样例输出】
45
59
6
13

【限制】
Time limit 1000 ms
Memory limit 30000 kB

【来源】
Japan 2004 Domestic

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
40
41
42
43
44
45
46
47
48
49
50
51
52
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL

int w,h, nxt[4][2] = {{1,0},{-1,0},{0,1},{0,-1}},x,y;
char map[25][25];
bool v[25][25];

int dfs(int i, int j) // 处于 (i,j), i是横坐标, j是列坐标
{
	int ans = 1;
	v[i][j] = true;
	for (int k = 0; k<4; k++)
	{
		int ni = i+nxt[k][0], nj = j+nxt[k][1];
		if (!v[ni][nj] && ni<h && nj<w && map[ni][nj]=='.')
		{
			ans+=dfs(ni, nj);
		}
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d%d", &w, &h), w||h)
	{
		memset(v, 0, sizeof(v));
		getchar();
		for (int i = 0; i<h; i++)
		{
			for (int j = 0; j<w; j++)
			{
				map[i][j] = getchar();
				if (map[i][j]=='@')
				{
					x = i;
					y = j; //(x,y)是人所在的位置
				}
			}
			getchar();
		}
		printf("%d\n", dfs(x,y));
	}
	return 0;
}

ac情况

Status Accepted
Memory 92kB
Length 845
Lang C++
Submitted 2019-08-23 11:03:08
Shared
RemoteRunId 20791053