首页 > 试题广场 >

没挡住洪水

[编程题]没挡住洪水
  • 热度指数：2693 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}吴铭市近日洪水肆虐，然而市政部门紧急在若干方格上砌起围墙是豆腐渣工程，被洪水中的强腐蚀性物质一氧化二氢分解了，只剩下了用 `#` 表示的空地。

\hspace{15pt}地图用大小为 N \times N 的字符矩阵描述：`'.'` 表示已经被洪水淹没的区域，`'#'` 表示空地。四联通的 `'#'` 组成一个区域。

\hspace{15pt}聪明睿智的吴铭市防洪抗灾紧急委员会官员在全市防洪抗灾紧急会议上指出，在接下来的一天中，洪水仍将上涨，所有与已经被洪水淹没的区域相邻（上下左右方向）的空地格子都会被淹没。请计算在此次上涨后，吴铭市中将有多少个区域被完全淹没。

输入描述:
\hspace{15pt}第一行输入整数 N\left(1\leqq N\leqq 1000\right)。
\hspace{15pt}随后 N 行，每行 N 个字符构成吴铭市的地图，只含 `'.'` 与 `'#'`。已知边界四条边全部为已经被洪水淹没的区域。


输出描述:
\hspace{15pt}输出一个整数，表示一天后会完全消失的空地区域数量。
示例1

输入

1
.

输出

0
算法知识视频讲解
添加回答
Veclanden头像 Veclanden
这题目在说啥，是给人看的？样例还就一个点？？？
发表于 2025-10-02 01:36:02 回复(0)
归虚梦演头像 归虚梦演
《强腐蚀性物质一氧化二氢》
发表于 2025-08-18 20:33:46 回复(0)
牛客270360877号头像 牛客270360877号
实例： 预期输出为1，题目确定没问题吗？明显所有格子都会被淹没，题干有：已知边界四条边全部为已经被洪水淹没的区域。
3
...
.##
...
发表于 2025-11-15 00:08:31 回复(1)
牛客973331176号头像 牛客973331176号
示例也太少了太抽象了
发表于 2025-08-30 11:50:48 回复(1)
上凡不思仙头像 上凡不思仙
很怀疑出题的人自己过几天能不能看懂自己写的这题目，你就这一实例鬼看的懂
发表于 2026-03-12 16:37:34 回复(1)
C++
爱看剧的花生米躺平又起来了头像 爱看剧的花生米躺平又起来了
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool is_water(vector<vector<char>>& map, int x, int y) {
    if (x < 0 || x >= map.size() || y < 0 || y >= map[0].size())return true;
    return map[x][y] == '.';
}//判断是否有水

bool ruin(vector<pair<int, int>> pos, vector<vector<char>>& map) {
    for (const auto& p : pos) {
        bool a = is_water(map, p.first - 1, p.second);
        bool b = is_water(map, p.first + 1, p.second);
        bool c = is_water(map, p.first, p.second - 1);
        bool d = is_water(map, p.first, p.second + 1);
        //如果某个点未被淹没，那么整个区域视为没被完全淹没
        if (!a && !b && !c && !d)return false;
    }
    return true;
}//判断该区域是否会被完全淹没

int main() {
    int n;
    cin >> n;
    vector<vector<char>>map(n, vector<char>(n, '0'));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
    vector<vector<char>>map1 = map;
    //area记录所有区域，区域包含所有的相邻空地
    vector<vector<pair<int, int>>>area;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map1[i][j] == '#') {
                vector<pair<int, int>>pos;
                queue<pair<int, int>>q;
                q.emplace(i, j);
                //寻找该区域的所有相邻空地
                while (!q.empty()) {
                    pair<int, int>p = q.front();
                    q.pop();
                    if (p.first < 0 || p.first >= map1.size() || p.second < 0 ||
                            p.second >= map1[0].size())continue;
                    if (map1[p.first][p.second] == '.')continue;
                    pos.emplace_back(p.first, p.second);
                    map1[p.first][p.second] = '.';
                    q.emplace(p.first - 1, p.second);
                    q.emplace(p.first + 1, p.second);
                    q.emplace(p.first, p.second - 1);
                    q.emplace(p.first, p.second + 1);
                }
                area.push_back(pos);
            }
        }
    }
    int count = 0;
    for (vector<pair<int, int>>& a : area) {
        if (ruin(a, map))count++;
    }//判断区域中有多少会被完全淹没
    cout << count << endl;
}
// 64 位输出请用 printf("%lld")
发表于 2026-02-18 21:29:51 回复(0)
juo1头像 juo1
给空地区域id，洪水后看剩下多少个id。这题主要注意的是有“瓶颈”的空地区域。一个空地区域不能变成两个区域。 
from collections import deque

n = int(input())
a = [list(input()) for _ in range(n)]
# Create a map to store which island ID each cell belongs to
island_map = [[0] * n for _ in range(n)]
dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]

def bfs_label(si, sj, label):
    q = deque([(si, sj)])
    island_map[si][sj] = label
    while q:
        i, j = q.popleft()
        for y, x in dirs:
            r, c = i + y, j + x
            if 0 <= r < n and 0 <= c < n and a[r][c] == '#' and island_map[r][c] == 0:
                island_map[r][c] = label
                q.append((r, c))

# 1. Label each original island with a unique ID (1, 2, 3...)
island_count = 0
for i in range(n):
    for j in range(n):
        if a[i][j] == '#' and island_map[i][j] == 0:
            island_count += 1
            bfs_label(i, j, island_count)

# 2. Identify which cells will survive the flood
# (A cell survives if it's NOT adjacent to any '.')
surviving_ids = set()
for i in range(n):
    for j in range(n):
        if a[i][j] == '#':
            is_submerged = False
            for y, x in dirs:
                r, c = i + y, j + x
                if r < 0&nbs***bsp;r >= n&nbs***bsp;c < 0&nbs***bsp;c >= n&nbs***bsp;a[r][c] == '.':
                    is_submerged = True
                    break
            
            # If this specific cell is NOT submerged, its island survives
            if not is_submerged:
                surviving_ids.add(island_map[i][j])

# 3. Total islands - Islands that had at least one surviving cell
print(island_count - len(surviving_ids))


发表于 2026-02-12 18:57:15 回复(0)
Python 3
Hero_123头像 Hero_123
解题没有让我醍醐灌顶，倒让我昏昏欲睡。
发表于 2025-12-09 16:18:39 回复(0)
nothing5头像 nothing5 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
    int N;
    cin >> N;
    
    vector<string> grid(N);
    for (int i = 0; i < N; i++) {
        cin >> grid[i];
    }
    
    // 标记一天后会淹没的 '#'
    vector<vector<bool>> will_flood(N, vector<bool>(N, false));
    
    // 第一次遍历：找出所有与 '.' 相邻的 '#'，标记为 will_flood
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == '#') {
                for (int d = 0; d < 4; d++) {
                    int ni = i + dx[d];
                    int nj = j + dy[d];
                    if (ni >= 0 && ni < N && nj >= 0 && nj < N && grid[ni][nj] == '.') {
                        will_flood[i][j] = true;
                        break;
                    }
                }
            }
        }
    }
    
    // 找出所有 '#' 的连通区域
    vector<vector<bool>> visited(N, vector<bool>(N, false));
    vector<vector<pair<int, int>>> regions;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == '#' && !visited[i][j]) {
                // BFS 找连通区域
                queue<pair<int, int>> q;
                vector<pair<int, int>> region;
                q.push({i, j});
                visited[i][j] = true;
                
                while (!q.empty()) {
                    auto [x, y] = q.front();
                    q.pop();
                    region.push_back({x, y});
                    
                    for (int d = 0; d < 4; d++) {
                        int nx = x + dx[d];
                        int ny = y + dy[d];
                        if (nx >= 0 && nx < N && ny >= 0 && ny < N && 
                            grid[nx][ny] == '#' && !visited[nx][ny]) {
                            visited[nx][ny] = true;
                            q.push({nx, ny});
                        }
                    }
                }
                regions.push_back(region);
            }
        }
    }
    
    // 统计完全消失的区域
    int vanished_count = 0;
    for (auto& region : regions) {
        bool all_flooded = true;
        for (auto [x, y] : region) {
            if (!will_flood[x][y]) {             
                all_flooded = false;
                break;
            }
        }
        if (all_flooded) {
            vanished_count++;
        }
    }
    
    cout << vanished_count << endl;
    
    return 0;
}

发表于 2025-10-31 14:56:42 回复(0)
C++
魔波旬头像 魔波旬 
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <utility>

using namespace std;
using pii = pair<int, int>;

int n;
vector<vector<char>> grid;
set<pii> visited;

const int dr[] = {0, 0, 1, -1};
const int dc[] = {1, -1, 0, 0};


vector<pii> BFS(pii start) {
    queue<pii> q;
    vector<pii> component; // 存储连通区域的所有坐标

    q.push(start);
    visited.insert(start);
    component.push_back(start); 

    while (!q.empty()) {
        pii cur = q.front();
        q.pop();

        for (int k = 0; k < 4; k++) {
            int nr = cur.first + dr[k];
            int nc = cur.second + dc[k];

            // 检查边界
            if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
            
            // 必须是'#' 并且未访问过
            if (grid[nr][nc] == '#' && !visited.count({nr, nc})) {
                visited.insert({nr, nc});
                q.push({nr, nc});
                component.push_back({nr, nc}); // 记录区域坐标
            }
        }
    }
    return component;
}
bool judge(const vector<pii>& component) {
    for (const auto& p : component) {
        int r = p.first;
        int c = p.second;
        bool is_survivor = true;

        // 检查四个方向
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            
            // 存活格子的四个邻居必须都是 '#'
            // 边界已知是 '.'，所以越界或遇到 '.' 都会导致该格子被淹没
            if (nr < 0 || nc < 0 || nr >= n || nc >= n || grid[nr][nc] == '.') {
                is_survivor = false;
                break;
            }
        }
        
        if (is_survivor) {
            // 找到一个四面都是'#'的格子，则该区域存活
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n;
    if (n == 1) {
        char c;
        cin >> c;
    }

    grid.resize(n, vector<char>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 找到一个新的未访问过的空地区域
            if (grid[i][j] == '#' && !visited.count({i, j})) {
                // 找到区域并判断是否存活
                vector<pii> component = BFS({i, j});
                // 如果区域不存活 (!judge)，则计数器 +1
                if (!judge(component)) {
                    cnt++;
                }
            }
        }
    }
    
    cout << cnt << endl;
    
    return 0;
}
快写死我了

发表于 2025-10-26 17:55:41 回复(0)
提交观点

问题信息

广度优先搜索(BFS)
难度：
10条回答 555浏览

热门推荐

相关试题

没挡住洪水

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号