AcWing 1113. 红与黑（BFS、DFS）

末蓝、 2023-01-06 14:54 147阅读 0赞

**上一篇博客：[LeetCode 4. 寻找两个正序数组的中位数][LeetCode 4.]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[AcWing 1113. 红与黑][AcWing 1113.]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  数据范围
     *  输入样例
     *  输出样例
 *  题解
 *   *  解题思路
     *  BFS解题代码
     *  DFS解题代码

# 题目信息 #

## 题目描述 ##

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。

请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

## 输入格式 ##

输入包括多个数据集合。每个数据集合的第一行是两个整数 `W` 和 `H`，分别表示 `x` 方向和 `y` 方向瓷砖的数量。在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下：  
 1）‘.’：黑色的瓷砖；  
 2）‘\#’：红色的瓷砖；  
 3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

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

## 输出格式 ##

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

## 数据范围 ##

**1 ≤ W, H ≤ 20**

## 输入样例 ##

> **6 9  
> . . . . \# .  
> . . . . . \#  
> . . . . . .  
> . . . . . .  
> . . . . . .  
> . . . . . .  
> . . . . . .  
> \#@ . . . \#  
> . \# . . \# .  
> 0 0**

## 输出样例 ##

> **45**

# 题解 #

## 解题思路 ##

本题是一个经典的 `Flood fill 算法（洪水填充算法）` ，有关该算法的详细解释请看之前的博客 [LeetCode 200.岛屿数量（DFS、BFS）][LeetCode 200._DFS_BFS]。但是这里要注意的是：输入的第一个数字是列，第二个数字是行，一定要注意输入的时候for循环不要写错了。 本题也可以使用 `DFS（深度优先搜索）` 解决。

## BFS解题代码 ##

#include<iostream>
    #include<queue>
    using namespace std;
    
    const int N = 25;
    char map[N][N];
    int n, m;
    int dx[] = { 1, 0, -1, 0}, dy[] = { 0, 1, 0 , -1};
    int ans;
    
    // 判断 (x, y) 是否在地图中
    bool inmap(int x, int y) { 
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    
    void bfs(int x, int y) { 
        queue<pair<int, int>> q;
        // 首先将当前位置改为 '#' 表示已经走过了
        map[x][y] = '#';
        // 将x, y加入到队列中
        q.push({ x, y});
        while (!q.empty()) { 
            // 取出队列的头结点
            pair<int, int> xy = q.front();
            q.pop();
            // 向4个方向拓展
            for (int i = 0; i < 4; i++) { 
                int x1 = xy.first + dx[i], y1 = xy.second + dy[i];
                // 如果下一个要走的点在地图内并且为黑色砖块，那么就将该点改为 '#' 并加入到队列中
                if (inmap(x1, y1) && map[x1][y1] == '.') { 
                    q.push({ x1, y1});
                    map[x1][y1] = '#';
                    ans++;
                }
            }
            
        }
    }
    
    int main() { 
        // 输入 n 列 m 行
        cin >> n >> m;
        while (n != 0  && m != 0) { 
            for (int i = 0; i < m; i++) { 
                for (int j = 0; j < n; j++) { 
                    cin >> map[i][j];
                }
            }
            
            queue<pair<int, int>> p;
            // 找到开始的地点
            int x, y;
            for (int i = 0; i < m; i++) { 
                for (int j = 0; j < n; j++) { 
                    if (map[i][j] == '@') { 
                        x = i;
                        y = j;
                        break;
                    }
                }
            }
            // bfs
            // 每次将 ans 初始化为 1，因为出发点算一个
            ans = 1;
            bfs(x, y);
            cout << ans << endl;
            cin >> n >> m;
        }
        return 0;
    }

## DFS解题代码 ##

#include<iostream>
    #include<queue>
    using namespace std;
    
    const int N = 25;
    char map[N][N];
    int n, m;
    int dx[] = { 1, 0, -1, 0}, dy[] = { 0, 1, 0 , -1};
    int ans;
    
    // 判断 (x, y) 是否在地图中
    bool inmap(int x, int y) { 
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    
    void dfs(int x, int y) { 
        map[x][y] = '#';
        for (int i = 0; i < 4; i++) { 
            int x1 = x + dx[i], y1 = y + dy[i]; 
            if (inmap(x1, y1) && map[x1][y1] == '.') { 
                ans++;
                dfs(x1, y1);
            }
        }
    }
    
    int main() { 
        // 输入 n 列 m 行
        cin >> n >> m;
        while (n != 0  && m != 0) { 
            for (int i = 0; i < m; i++) { 
                for (int j = 0; j < n; j++) { 
                    cin >> map[i][j];
                }
            }
            
            queue<pair<int, int>> p;
            // 找到开始的地点
            int x, y;
            for (int i = 0; i < m; i++) { 
                for (int j = 0; j < n; j++) { 
                    if (map[i][j] == '@') { 
                        x = i;
                        y = j;
                        break;
                    }
                }
            }
            // dfs
            // 每次将 ans 初始化为 1，因为出发点算一个
            ans = 1;
            dfs(x, y);
            cout << ans << endl;
            cin >> n >> m;
        }
        return 0;
    }

--------------------

> 未完待续，持续更新中……  
> ![不说了 读书][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]

[LeetCode 4.]: https://ac-fun.blog.csdn.net/article/details/112069614
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[AcWing 1113.]: https://www.acwing.com/problem/content/1115/
[LeetCode 200._DFS_BFS]: https://ac-fun.blog.csdn.net/article/details/108334624
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: /images/20221119/e247983447754d60b1425512ffcd2a1a.png