首页 > 试题广场 >

挡住洪水

[编程题]挡住洪水
  • 热度指数：2950 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}吴铭市近日洪水肆虐，洪水从地图外部渗入。市政部门在若干方格上砌起围墙，用 `*` 表示。若某片空地区域不与地图边界四联通（上下左右方向），则不会被洪水淹没，视为安全空地。

\hspace{15pt}地图用大小为 x \times y 的字符矩阵描述：`'*'` 表示围墙，`'0'` 表示空地。所有相互四联通的 `'0'` 构成一个区域。请统计所有安全空地格子的数量之和（即所有不与边界四联通的 `'0'` 的总数）。

输入描述:
\hspace{15pt}第一行输入两个整数 x,y\left(1\leqq x,y\leqq 500\right)。
\hspace{15pt}接下来 x 行，每行 y 个字符，组成围墙建设图，仅含 `'*'` 与 `'0'`。


输出描述:
\hspace{15pt}输出一个整数，表示所有安全空地格子的总数。
示例1

输入

2 2
**
**

输出

0
算法知识视频讲解
添加回答
Python3
tjss666一号头像 tjss666一号
这个题确实有歧义，这个地方统计的是安全区域中的0的个数 
n,m = map(int, input().split())
if 1 <= n < 3&nbs***bsp;1 <= m < 3:
    print(0)
    quit()
s,dirs,sum1 = [],[(1,0),(0,1),(-1,0),(0,-1)],0
for i in range(n):
    s.append(list(input().replace('*','X')))      
def dfs(i,j):
    stack = [(i,j)]
    an = True
    shu = 1
    while stack:
        nx,ny = stack.pop()
        for dx,dy in dirs:
            x = nx+dx
            y = ny+dy
            if s[x][y] == '0':
                if x == 0&nbs***bsp;x == n-1&nbs***bsp;y == 0&nbs***bsp;y == m-1:
                    s[x][y] = 'X'
                    an = False
                elif 0 < x < n-1 and 0 < y < m-1:
                    s[x][y] = 'X'
                    shu += 1
                    stack.append((x,y))
    if an:
        return shu
    else:
        return 0
for i in range(n):
    for j in range(m):
        if s[i][j] == '0' and 0 < i < n-1 and 0 < j < m-1:
            s[i][j] = 'X'
            sum1 += dfs(i,j)
print(sum1)
首先n和m随便一个小于3都绝对不行，因为这个题的在边界上所有的0都会导致区域无效，因为只需要解决一次案例所以我用的quit直接退出，如果数据组数很多就不要这样做。然后就是经典的列表、dirs方向和和sum1。为了在过程中输出矩阵内容更直观，我把*换成了X，这样所有的元素都会很齐整。然后就是绝对dfs加栈遍历，对每一个dfs(i,j)记为一个区域，所以开头就写出an和shu，之后不用管s[x][y]为X的情况，因为对题目没有如何影响，你可以想一想，假如有一个区域含0，他不是安全区域的可能只有有边界0的情况，不然就一定是安全的，所以判断边界，如果不是边界就计数并append方便循环，最后return 0 或者 shu也是经典方法了，这样方便sun1累加。注意最后一定要是0而且不是边界的时候才dfs，这是寻找安全区域的基本条件，并且就是因为提前找到了一个0，dfs中shu必须从1开始
发表于 2025-08-17 11:35:57 回复(0)
lahm66头像 lahm66
打卡能添加难度就好了，希望打卡简单点，不要太难，可以稍微难一点
发表于 2025-11-03 14:04:53 回复(0)
C
人生有三乐头像 人生有三乐
我尼玛，我问一圈AI，AI都***晕了，AI都不懂出题人在讲什么，然后再看一眼讨论区，原来是出题人出错了。。。。。本题其实是找所有安全区域中’0‘的个数 
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
//BFS用队列，c语言没有队列，用数组做一次队列吧，
//思路只要探索到超出边界，说明没有墙，所以就不安全。记录记录这个区域的最大最小行和列，然后看看有没有超出边界就行了。
 
typedef struct{ //坐标的位置
  int x;
  int y; 
} pos;
 
//数组做一次队列
pos queue[250000];
int queue_front=0;  //队头
int queue_end=0;   //队尾
 
//判断队列是不是空的
bool is_empty_queue()
{
    if (queue_front==queue_end) {
        return true;
    }
    return false;
}
 
//入队，队列只能后进先出，返回是否入队成功
bool queue_push(pos temp)
{
    if(queue_end==250000)
    {return false;}
    queue[queue_end]=temp;
    queue_end++;
    return true;
     
}
 
//出队，队列只能后进先出
pos queue_pop()
{
    pos temp=queue[queue_front];
    queue_front++;
    return temp;
}
 
//队列初始化归零
void queue_init(){
    queue_front=0;  //队头
    queue_end=0;   //队尾
}
 
int safe_count=0;//安全区域的数量
char** matrix;
int n,m;//矩阵行和列的长度
//找连通区域
void bfs(int x,int y)//对哦，这个x和y是起点不是头节点的位置
{
    int min_x=x;int max_x=x;int min_y=y;int max_y=y;
    int zero_count = 0;  // 统计这个区域的0的个数
    pos start={.x=x,.y=y};
    matrix[start.x][start.y]='*';  //入队时阻塞，不然等到出队，后面的队会重复进入到这个位置
    queue_push(start);  //初始节点入队列
    bool touch_boundary = false;  // 新增：标记是否接触边界
    zero_count++;
    while (!is_empty_queue()) {  //当头节点不空，取出头节点
        pos temp=queue_pop();
        //matrix[temp.x][temp.y]='*';  //阻塞这个位置不给走
         
        //判断这个点是否超出最小最大行列。
        if (temp.x<min_x) {
            min_x=temp.x;
        }
        if (temp.x>max_x) {
            max_x=temp.x;
        }
        if (temp.y<min_y) {
            min_y=temp.y;
        }
        if (temp.y>max_y) {
            max_y=temp.y;
        }
 
        // 检查是否接触边界
        if (temp.x == 0 || temp.x == n-1 || temp.y == 0 || temp.y == m-1) {
            touch_boundary = true;
        }
 
        //往上下左右探索
        if (temp.x-1>=0&&matrix[temp.x-1][temp.y]=='0') {  //往上探索
            //把这个点加入队列
            pos t={.x=temp.x-1,.y=temp.y};
            matrix[t.x][t.y]='*';
            queue_push(t);
            zero_count++;
        }
        if (temp.x+1<n&&matrix[temp.x+1][temp.y]=='0') {  //往下探索
            //把这个点加入队列
            pos t={.x=temp.x+1,.y=temp.y};
            matrix[t.x][t.y]='*';
            queue_push(t);
            zero_count++;
        }
        if (temp.y-1>=0&&matrix[temp.x][temp.y-1]=='0') {  //往下探索
            //把这个点加入队列
            pos t={.x=temp.x,.y=temp.y-1};
            matrix[t.x][t.y]='*';
            queue_push(t);
            zero_count++;
        }
        if (temp.y+1<m&&matrix[temp.x][temp.y+1]=='0') {  //往下探索
            //把这个点加入队列
            pos t={.x=temp.x,.y=temp.y+1};
            matrix[t.x][t.y]='*';
            queue_push(t);
            zero_count++;
        }
    }
 
    //遍历完看连通区域是否碰到边界
    if (min_x>0&&max_x<n-1&&min_y>0&&max_y<m-1) {
        safe_count+=zero_count;  //安全区域加1
    }
    // 判断安全区域：没有接触任何边界
    // if (!touch_boundary) {
    //     safe_count++;
    // }
}
 
int main() {
    int x,y;
    scanf("%d %d",&x,&y);
    n=x;
    m=y;
    //初始化矩阵
    matrix=malloc(sizeof(char*)*x);
    for (int i=0; i<x; i++) {
        matrix[i]=malloc(sizeof(char)*(y+1));
        scanf("%s",matrix[i]);
        //printf("%s\n",matrix[i]);
    }
 
    //遍历所有所有区域，统计最小最大行和列
    for (int i=0; i<x; i++) {
        for (int j=0; j<y; j++) {
            if (matrix[i][j]=='0') {  //这个位置为0才能走
                queue_init();//队列归零
                bfs(i, j);//以i，j作为起点找连通区域
            }
             
        }
    }
    printf("%d",safe_count);
    return 0;
}



发表于 2025-10-17 16:19:21 回复(0)
粗心的牛油果爱健身头像 粗心的牛油果爱健身
这题简直一排胡言啊.明明是统计除了边界0连通的部分外的0的个数, 怎么说的好像是除了边界0连通的部分外的区域个数了, 这完全不一个意思啊. 如果是以区域算的话, 处理完边界连通的0区域之后, 还要再统计非边界连通的区域个数,那样结果会少很多的. 脑残描述
发表于 2025-09-07 15:44:50 回复(0)
Java
牛客319870016号头像 牛客319870016号 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static boolean[][] visit = new boolean[500][500];
    private static int[][] move = new int[][] {{0, 0, 1, -1}, {1, -1, 0, 0}};
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int row = in.nextInt();
        int col = in.nextInt();
        char[][] array = new char[row][col];

        for (int i = 0; i < row; i++) {
            String line = in.next();
            for (int j = 0; j < col; j++) {
                array[i][j] = line.charAt(j);
            }
        }

        int total = 0;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (!visit[i][j] && array[i][j] == '0' && i > 0 && i < row - 1 && j > 0 &&
                        j < col - 1) {
                    queue.offer(new int[] {i, j});
                    visit[i][j] = true;
                    total += getNum(array, queue, row, col);
                }
            }
        }
        System.out.print(total);
    }

    private static int getNum(char[][] array, Queue<int[]> queue, int row,
                              int col) {
        int num = 1;
        boolean isBlock = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] position = queue.poll();
                int px = position[0];
                int py = position[1];

                for (int j = 0; j <= 3; j++) {
                    int newPx = px + move[0][j];
                    int newPy = py + move[1][j];

                    if ((newPx == 0 || newPx == row - 1 || newPy == 0 || newPy == col - 1) &&
                            array[newPx][newPy] == '0') {
                        isBlock = false;
                        continue;
                    }

                    if (newPx > 0 && newPx < row - 1 && newPy > 0 && newPy < col - 1 &&
                            !visit[newPx][newPy] && array[newPx][newPy] == '0') {
                        visit[newPx][newPy] = true;
                        queue.offer(new int[] {newPx, newPy});
                        num++;
                    }
                }
            }
        }
        return isBlock ? num : 0;
    }
}

发表于 2025-12-13 09:26:30 回复(0)
C++
nothing5头像 nothing5
这个题目既然说了被围墙或着地图边界包围的空地视为安全区域，那么我理解成就直接求空地区域的数量，即案例中1行1列且为空地，不应该输出1吗，上下左右被地图边界包围，难道不是安全区域吗，然后我排除边界的情况，只通过7组案例，真的看不懂这个题的意思 
#include <iostream>
#include <vector>
using namespace std;

//方向数组
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void dfs(int x, int y, vector<string>& gride, vector<vector<bool>>& visited,
         int n, int m, bool& touch) {
    visited[x][y] = true;

    if (x == 0 || y == 0 || n - 1 == x || m - 1 == y) {
        touch = true;
    }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                gride[nx][ny] == '0' && visited[nx][ny] == false) {
            visited[nx][ny] = true;
            dfs(nx, ny, gride, visited, n, m, touch);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> gride(n);
    for (int i = 0; i < n; i++) {
        cin >> gride[i];
    }

    int count_area = 0;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            bool touch = false;
            if (gride[i][j] == '0' && visited[i][j] == false) {
                dfs(i, j, gride, visited, n, m, touch);
                if (!touch) {
                    count_area ++;
                }
            }
        }
    }

    cout << count_area << endl;
}
// 64 位输出请用 printf("%lld")

发表于 2025-10-30 16:33:08 回复(0)
C++
我乃_三转巅峰头像 我乃_三转巅峰
滋，原来求的不是连通的，而是一个像素就+1了 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'
#define mod 998244353
#define N 1005

int n,m;
char mp[N][N];
int dx[]={-1,0,0,1};
int dy[]={0,-1,1,0};
int ans=0;
//从四周走，只有围墙*才能挡住水
//#：边界的0
void dfs(int x,int y){
    mp[x][y]='#';
    for(int i=0;i<4;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx<1||yy<1||xx>n||yy>m||(mp[xx][yy]=='*'))  
                continue;
        if(mp[xx][yy]=='0')
        dfs(xx,yy);
    }
    return ;
}
//找出剩下的个数
// void dfs2(int x,int y){
//     mp[x][y]='1';
//     for(int i=0;i<4;i++){
//         int xx=x+dx[i], yy=y+dy[i];
//         if(xx<1||yy<1||xx>n||yy>m||mp[xx][yy]!='0')
//             continue;
//        dfs2(xx,yy);
//     }
// }

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>mp[i][j];
    
    for(int i=1;i<=n;i++){
        if(mp[i][1]=='0')
        dfs(i,1);
        if(mp[i][m]=='0')
        dfs(i,m);
    }
    for(int i=1;i<=m;i++){
        if(mp[1][i]=='0')
        dfs(1,i);
        if(mp[n][i]=='0')
        dfs(n,i);
    }
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++)
    //         cout<<mp[i][j];

    //     cout<<endl;
    // }
        
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(mp[i][j]=='0'){
      //          dfs2(i,j);
                    ans++;
            }
    
    cout<<ans<<endl;
    return 0;
}

发表于 2025-09-16 20:43:59 回复(0)
Go
草海桐头像 草海桐 
package main

/* 
    先把边界为'0'的地方都BFS标记一次（会被淹没的'0'）
    然后再次BFS_未被标记的'0'，计算安全的'0'的个数
 */

import (
    "fmt"
)

type Node struct{
    i,j int
}

func main() {
    var n,m int
    fmt.Scanf("%d %d",&n, &m)
    var k = make([][]byte, n)
    var v = make([][]bool, n)
    var s string
    for i:=0;i<n;i++{
        k[i] = make([]byte, m)
        v[i] = make([]bool, m)
        fmt.Scanf("%s", &s)
        k[i] = []byte(s) 
    }

    dist:= [][]int{{0,1}, {0,-1}, {1,0}, {-1,0}}
    
    var cur Node
    var queue []Node
    var result, ni, nj int
    var BFS func(i, j int)

    BFS = func(i, j int){ // 标记会被淹没的'0'
        queue = []Node{{i,j}}
        for len(queue) > 0{
            cur = queue[0]
            queue = queue[1:]

            for _, d := range dist{
                ni = cur.i + d[0]
                nj = cur.j + d[1]
                if ni<0 || ni>=n || nj<0 || nj>=m || v[ni][nj] || k[ni][nj] == '*'{
                    continue
                }
                v[ni][nj] = true
                queue = append(queue, Node{ni,nj})
            }
        }
    }

    var BFS_ func(i, j int) // 累计安全的'0'的个数
    BFS_ = func(i, j int){
        queue = []Node{{i,j}}
        for len(queue) > 0{
            cur = queue[0]
            queue = queue[1:]

            for _, d := range dist{
                ni = cur.i + d[0]
                nj = cur.j + d[1]
                if ni<0 || ni>=n || nj<0 || nj>=m || v[ni][nj] || k[ni][nj] == '*'{
                    continue
                }
                v[ni][nj] = true
                result++
                queue = append(queue, Node{ni,nj})
            }
        }
    }

    // 标记会被淹没的区域
    for i:=0;i<n;i++{
        if k[i][0] == '0' && !v[i][0] {
            v[i][0] = true
            BFS(i,0)
        }
        if k[i][m-1] == '0' && !v[i][m-1]{
            v[i][m-1] = true
            BFS(i,m-1)
        }
    }
    for i:=0;i<m;i++{
        if k[0][i] == '0' && !v[0][i] {
            v[0][i] = true
            BFS(0,i)
        }
        if k[n-1][i] == '0' && !v[n-1][i]{
            v[n-1][i] = true
            BFS(n-1,i)
        }
    }

    for i:=0;i<n;i++{
        for j:=0;j<m;j++{
            if k[i][j] == '0' && !v[i][j]{
                v[i][j] = true
                result++
                BFS_(i,j)
            }
        }
    }
    fmt.Print(result)
}


发表于 2025-09-07 19:32:50 回复(0)
Python3
xjh_ustc头像 xjh_ustc 
from collections import deque
n,m = map(int,input().split())
grid = []
for i in range(n):
    grid.append(input().strip())
visited = [[False]*m for _ in range(n)]
dire = [(-1,0),(1,0),(0,-1),(0,1)]
cnt = 0
for i in range(n):
    for j in range(m):
        if grid[i][j] == '0' and not visited[i][j]:
            dq = deque([(i,j)])
            visited[i][j] = True
            is_safe = True
            size = 1
            while dq:
                x,y = dq.popleft()
                if x==0 or x==n-1 or y==0 or y==m-1:
                    is_safe = False
                for dx,dy in dire:
                    nx,ny=x+dx,y+dy
                    if 0<=nx<n and 0<=ny<m:
                        if not visited[nx][ny] and grid[nx][ny]=='0':
                            visited[nx][ny]=True
                            dq.append((nx,ny))
                            size += 1
            if is_safe:
                cnt +=size
print(cnt)
发表于 2025-09-04 19:26:34 回复(0)
牛客973331176号头像 牛客973331176号
原来这道题是在找不和边界相邻的0的个数 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n,m;
    cin>>n>>m;
    vector<string> board(n);
    queue<pair<int,int>> q;
    for(int i=0;i<n;i++)
    {
        cin>>board[i];
    }
    for(int i=0;i<n;i++)
    {
        if(board[i][0]=='0')
        {
            q.push({i,0});
            board[i][0]='a';
        }
         if(board[i][m-1]=='0')
        {
            q.push({i,m-1});
            board[i][m-1]='a';
        }
    }
     for(int i=1;i<m-1;i++)
    {
        if(board[0][i]=='0')
        {
            q.push({0,i});
            board[0][i]='a';
        }
         if(board[n-1][i]=='0')
        {
            q.push({n-1,i});
            board[n-1][i]='a';
        }
    }
    while(!q.empty())
    {
        auto [x,y]=q.front();
        q.pop();
        if(x+1<=n-1 && board[x+1][y]=='0')
        {
            q.push({x+1,y});
            board[x+1][y]='a';
        }
        if(x-1>=0 && board[x-1][y]=='0')
        {
            q.push({x-1,y});
            board[x-1][y]='a';
        }
        if(y+1<=m-1 && board[x][y+1]=='0')
        {
            q.push({x,y+1});
            board[x][y+1]='a';
        }
        if(y-1>=0 && board[x][y-1]=='0')
        {
            q.push({x,y-1});
            board[x][y-1]='a';
        }
    }

   int count=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(board[i][j]=='0')
            count++;
        }
    }
    cout<<count<<endl;
}
// 64 位输出请用 printf("%lld")

发表于 2025-08-30 11:37:05 回复(0)
牛客348448733号头像 牛客348448733号
2 2
**
*0
感觉题目有问题，不理解为什么这个用例应该是0呢？
发表于 2025-08-15 17:21:44 回复(0)
提交观点

问题信息

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

热门推荐

相关试题

挡住洪水

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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