红与黑

题目描述

信息学奥赛一本通（C++版）在线评测系统 有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入

包括多组数据。每组数据的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下:

1）‘.’：黑色的瓷砖；

2）‘#’：红色的瓷砖；

3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每组数据中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。

输出

对每组数据，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

输入样例

6 9 
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0

输出样例

45

思路

定义一个全局变量res, 在更新st数组时同时把res++即可。

代码

const int N = 22;
char g[N][N];
int res;
int n, m;
bool st[N][N];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
 
void dfs(int x, int y)
{
    if (g[x][y] == '#')
        return;
    st[x][y] = true;
    res++;
    for (int i = 0; i < 4; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 | b >= m)
            continue;
        if (st[a][b])
            continue;
        dfs(a, b);
    }
}
 
inline void findStart(int &xa, int &ya)
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '@')
            {
                xa = i, ya = j;
                return;
            }
}
 
int main()
{
    while (cin >> m >> n, m || n)
    {
        for (int i = 0; i < n; i++)
            cin >> g[i];
        res = 0;
        memset(st, false, sizeof st);
        int x, y;
        findStart(x, y);
        dfs(x, y);
        cout << res << endl;
    }
    return 0;
}