【题解-洛谷】P1506 拯救oibh总部

发布于：2025-06-09 ⋅ 阅读:(20) ⋅ 点赞:(0)

题目：P1506 拯救oibh总部

题目背景

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

题目描述

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

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

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

输出 #2

说明/提示

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

代码

#include<iostream>

using namespace std;

typedef pair<int, int> PII;
const int Maxx = 500 + 10, Maxy = 500 + 10;

int x, y, hh, tt = -1, vis[Maxx][Maxy], sum;
char map[Maxx][Maxy];
PII q[Maxx * Maxy];

void init(){
    hh = 0, tt = -1;
}

void insert(int i, int j){
    q[++ tt] = {i, j};
}

void dele(){
    hh ++;
}

bool isempty(){
    return hh > tt;
}

void bfs(int sx, int sy){
    init();
    insert(sx, sy);
    vis[sx][sy] = 1;
    map[sx][sy] = '*';

    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    while(!isempty()){
        auto t = q[hh];
        dele();

        for(int i = 0; i < 4; i ++){
            int newx = t.first + dx[i], newy = t.second + dy[i];
            if(newx >= 0 && newx < x && newy >= 0 && newy < y && map[newx][newy] == '0' && !vis[newx][newy]){
                insert(newx, newy);
                vis[newx][newy] = 1;
                map[newx][newy] = '*';
            }
        }
    }
}

int main(){
    scanf("%d%d", &x, &y);
    for(int i = 0; i < x; i ++){
        scanf("%s", map[i]);
    }

    for(int i = 0; i < x; i ++){
        if(map[i][0] == '0' && !vis[i][0]){ // 第一列
            bfs(i, 0);
        }
        if(map[i][y - 1] == '0' && !vis[i][y - 1]){ // 最后一列
            bfs(i, y - 1);
        }
    }
    for(int j = 0; j < y; j ++){
        if(map[0][j] == '0' && !vis[0][j]){ // 第一行
            bfs(0, j);
        }
        if(map[x - 1][j] == '0' && !vis[x - 1][j]){ // 最后一行
            bfs(x - 1, j);
        }
    }

    for(int i = 0; i < x; i ++){
        for(int j = 0; j < y; j ++){
            if(map[i][j] == '0'){
                sum ++;
            }
        }
    }

    printf("%d", sum);
    return 0;
}

结果

在这里插入图片描述

坑

输出的区域之和是指每一个"0"之和