洛谷 P1506 拯救 oibh 总部

P1506 拯救 oibh 总部 - 洛谷 | 计算机科学教育新生态

题目来源

洛谷

题目内容

拯救oibh总部

题目背景

oibh 总部突然被水淹没了！现在需要你的救援……

题目描述

oibh 被突来的洪水淹没了，还好 oibh 总部有在某些重要的地方起一些围墙。用 * 号表示，而一个四面被围墙围住的区域洪水是进不去的。

oibh 总部内部也有许多重要区域，每个重要区域在图中用一个 0 表示。

现在给出 oibh 的围墙建设图，问有多少个没被洪水淹到的重要区域。

输入格式

第一行为两个正整数 $x,y$。

接下来 $x$ 行，每行 $y$ 个整数，由 * 和 0 组成，表示 oibh 总部的建设图。

输出格式

输出没被水淹没的 oibh 总部的 0 的数量。

样例 #1

样例输入 #1

4 5
00000
00*00
0*0*0
00*00

样例输出 #1

1

样例 #2

样例输入 #2

5 5
*****
*0*0*
**0**
*0*0*
*****

样例输出 #2

5

提示

对于 $100\%$ 的数据，$1\le x,y\le 500$。

知识点

BFS 染色法

题目思路

1. 从最外面的一圈往里遍历 bfs 模拟被洪水淹到的效果
2. 然后将淹到的改为 2，遇到围墙则跳过
3. 然后统计最终剩余多少个基地 (0 值) 没被淹没到 输出答案
4. 统计答案，我这里没有遍历最外圈，因为外圈有 0 就会被淹没到，可以不管，就算是小优化一下

AC代码

//
// Created by Jisam on 2024/7/12.
//
#include <bits/stdc++.h>
// 定义一对字符串和整数的配对类型
#define PSI pair<string,int>
// 定义一对整数的配对类型
#define PII pair<int,int>
// 定义长整型别名
#define i64 long long
// 使用标准库命名空间
using namespace std;

// 定义迷宫的最大尺寸
const int N = 500 + 5;
// 存储答案的变量
int ans;
// 存储迷宫布局的二维数组
char ma[N][N];
// 标记某个位置是否被访问过的二维数组
int vis[N][N];
// x方向的移动选项
int dx[] = {-1,1,0,0};
// y方向的移动选项
int dy[] = {0,0,-1,1};
// 迷宫的行数和列数
int n,m;

/**
 * @brief 广度优先搜索函数，用于寻找与起点相连的空白区域
 * @param x 起点的x坐标
 * @param y 起点的y坐标
 */
void bfs(int x,int y){
    // 使用队列来进行广度优先搜索
    queue<PII> q;
    q.push({x,y});
    while (q.size())
    {
        // 取出队列头部的元素
        int tx = q.front().first;
        int ty = q.front().second;
        q.pop();
        // 如果当前位置是障碍物，则跳过
        if(ma[tx][ty] == '*'){
            continue;
        }
        // 遍历四个可能的移动方向
        for(int i = 0 ; i < 4 ; i ++){
            int fx = tx + dx[i];
            int fy = ty + dy[i];
            // 如果移动后的位置有效，并且是空白区域且未被访问过
            if(fx >= 0 && fy >= 0 && fx < n && fy < m && ma[fx][fy] == '0' && !vis[fx][fy] )
            {
                // 标记该位置为已访问
                ma[fx][fy] = '2';
                vis[fx][fy] = 1;
                // 将该位置加入队列继续搜索
                q.push({fx,fy});
            }
        }

    }
}

/**
 * @brief 主函数，负责读入迷宫信息并计算答案
 */
void solve() {
    // 读入迷宫的行数和列数
    cin >> n >> m;
    // 读入迷宫的具体布局
    for(int i = 0; i < n ; i ++)
    {
        for(int j = 0 ; j < m ; j ++)
        {
            cin >>ma[i][j];
        }
    }
    // 从每一面开始，进行广度优先搜索
    for(int i = 0 ;i < n ; i ++){
        if(!vis[i][0] && ma[i][0] != '*') bfs(i,0);
        if(!vis[i][m] && ma[i][m] != '*')  bfs(i,m);
    }
    for(int i = 0 ;i < m ; i ++){
        if(!vis[0][i]&&ma[0][i] != '*')  bfs(0,i);
        if(!vis[n][i]&&ma[n][i] != '*')  bfs(n,i);
    }
    // 统计剩余的未被搜索到的空白区域数量
    // 这里没有遍历最外圈，因为外圈有0就会被淹没到，可以不管，就算是小优化一下 i: 1 ~ n -1  j: 1 ~ m - 1
    for(int i = 1; i < n - 1; i ++)
    {
        for(int j = 1 ; j < m - 1; j ++)
        {
            if(ma[i][j] == '0')ans ++;
        }
    }
    // 输出答案
    cout << ans;
}

// 程序入口
int main() {
    // 关闭同步标准输入输出，提高效率
    ios::sync_with_stdio(false);
    // 解除cin与cout的绑定，提高效率
    cin.tie(nullptr);
    // 调用主函数解决问题
    solve();
    // 程序正常结束
    return 0
}