C++描述 1113. 红与黑

  大家好，我叫亓官劼（qí guān jié ），在CSDN中记录学习的点滴历程，时光荏苒，未来可期，加油~博主目前仅在CSDN中写博客，唯一博客更新的地址为：亓官劼的博客 ，同时正在尝试在B站中做一些内容分享，B站主页为： 亓官劼的B站主页

本文原创为亓官劼，请大家支持原创，部分平台一直在恶意盗取博主的文章！！！
若需联系博主，可以联系本人微信：qiguanjie2015

---

题目

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。

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

输入格式

输入包括多个数据集合。

每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。

在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下

1）‘.’：黑色的瓷砖；
2）‘#’：红色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

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

输出格式

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

数据范围

1≤W,H≤20

输入样例：

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

输出样例：

45

题解思路

这里即求从@位置开始，最大连续的.的数量。这里有三种方法来解决：BFS、DFS、并查集。这里提供BFS和DFS的解法实现，并查集的实现也非常简单，大家可以自行实现。

如果是使用BFS来实现的话，那么就是一层一层的来查找一圈是否可以扩展，如果可以扩展，则加入待扩展队列，使用res来记录最大连通数，每次取待扩展结点时，res++，直到所有结点都扩展完毕，待扩展队列为空时，获得当前最大连通数。

BFS实现

#include<iostream>
#include<queue>
#include<algorithm>
#define x first
#define y second
using namespace std;
int n,m;
typedef pair<int, int> PII;
// 存储输入数据
char g[25][25];
int bfs(int sx,int sy){
    int res = 0;
    queue<PII> q;
    // 当前位置加入队列
    q.push({sx,sy});
    g[sx][sy] = '$';// 设置为访问过
    // 方向偏移量
    int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
    while(q.size()){
        // 出队一个带扩展结点，res++
        auto t = q.front();
        q.pop();
        // 记录可扩展数
        res++;
        for(int i = 0 ; i < 4; i++){
            int a = t.x + dx[i], b = t.y + dy[i];
            // 当前不可扩展时，直接continue
            if(a < 0 || a >= n || b < 0 || b >= m || g[a][b] != '.')
                continue;
            else{
                g[a][b] = '$';// 设置为访问过
                q.push({a,b});// 加入待扩展队列
            }
        }
    }
    return res;
}
int main(){
    
    while(cin>>m>>n , n || m){
        for (int i = 0; i < n; i ++ ) cin >> g[i];
        int x,y;
        for(int i = 0; i < n; i++){
            for(int j = 0 ; j < m; j++){
                // 找到当前位置
                if(g[i][j] == '@'){
                    x = i;
                    y = j;
                }
            }
        }
        // 通过bfs搜索，返回结果
        cout<<bfs(x,y)<<endl;
    }
    return 0;
    
}

DFS实现

dfs实现更简短，但是会有爆栈的风险。

#include<iostream>
using namespace std;
int n,m;
// 存储输入数据
char g[25][25];
// 方向偏移量
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
int dfs(int x,int y){
    int res = 1;
    g[x][y]  = '$';//使用`$`标记为访问过
    // 查看上、下、左、右四个方向
    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 && g[a][b] == '.'){
            res += dfs(a,b);
        }
    }
    return res;
}
int main(){
    while(cin>>m>>n , n || m){
        for (int i = 0; i < n; i ++ ) cin >> g[i];
        int x,y;
        for(int i = 0; i < n; i++){
            for(int j = 0 ; j < m; j++){
                // 找到当前位置
                if(g[i][j] == '@'){
                    x = i;
                    y = j;
                }
            }
        }
        // 通过bfs搜索，返回结果
        cout<<dfs(x,y)<<endl;
    }
    return 0;
    
}