当前位置：首页 > news >正文

Red and Black （DFS）

news 来源：原创 2024/4/30 14:41:16

有一个长方形的房间，覆盖了正方形的磁砖。每块磁砖的颜色，要么是红色，要么是黑色。一名男子站在一块黑色的磁砖上。他可以从一块磁砖移至相邻四块磁砖中的某一块。但是，他不允许在红色磁砖上移动，他只允许在黑色磁砖上移动。

编写一个程序，使得他允许重复上述的移动，判断他所能到达的黑色磁砖的数量。

输入

输入由多个数据集组成。数据集的起始行包含了两个正整数 W 和 H；W 和 H 分别是 x- 和 y- 方向的磁砖数量。W 和 H 不超过 20 。

在数据集中，还有 H 行，每行包含了 W 个字符。每个字符按如下方式表示一块磁砖的颜色。

'.' - 一块黑色的磁砖
'#' - 一块红色的磁砖
'@' - 一名男子，站在一块黑色磁砖上 (在一个数据集中，恰好出现一次)

以包含两个 0 的一行，表示输入结束。

输出

对于每个数据集，程序应当输出一行，包含他从初始磁砖所能抵达的磁砖数量 (包括初始磁砖自身)。

示例输入

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

示例输出

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<algorithm>
#include<functional>
#include<sstream>
int W, H;
char z[21][21];

int f(int x, int y)
{
    if (x < 0 || x >= W || y < 0 || y >= H)
        return 0;
    if (z[x][y] == '#')
    {
        return 0;
    }
    else
    {
        z[x][y] = '#';
        return 1 + f(x - 1, y) + f(x + 1, y) + f(x, y - 1) + f(x, y + 1);
    }
}
int main(int argc, char* argv[])
{
    int i, j, num;
    while (scanf("%d%d", &H, &W) && W != 0 && H != 0)
    {
        for (i = 0; i < W; i++)
            scanf("%s", z[i]);

        for (i = 0; i < W; i++)
            for (j = 0; j < H; j++)
                if (z[i][j] == '@') printf("%d\n", f(i, j));
    }
    return 0;
}