P1451 求细胞数量

May 8, 2026 · 5 分钟阅读 · 深度优先搜索 Flood Fill 图论 ·

文章目录

题目信息

字段	内容
题号	P1451
难度	入门
知识点	DFS、Flood Fill、图的连通块

题目描述

给定一个 N × M 的网格，每个格子中有一个数字（0 或非 0）。数字不为 0 的格子属于"细胞"，上下左右四个方向相连的细胞属于同一个细胞。求网格中共有多少个细胞。

解题思路

核心思想：Flood Fill（洪水填充）

从每个未访问的细胞格子出发，用 DFS 沿上下左右四个方向递归遍历，将所有与之相连的格子全部标记为已访问（b[x][y] = false），这样就完成了一个细胞的计数。最后遍历整个网格，统计执行了多少次 DFS，即为细胞总数。

初始: 所有非 '0' 格子 b=true
遍历:
  若 b[i][j] == true → dfs(i,j) → cnt++
  dfs 会将整块连通区域全部标记为 false（已访问）
  后续格子不会重复进入同一连通块

完整代码

C++

#include <iostream>
using namespace std;

int n, m, cnt;
bool b[110][110];
char ch;

void dfs(int x, int y) {
    if (!b[x][y]) return;
    b[x][y] = false;
    dfs(x - 1, y);
    dfs(x + 1, y);
    dfs(x, y - 1);
    dfs(x, y + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> ch;
            if (ch != '0') b[i][j] = true;
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (b[i][j]) {
                dfs(i, j);
                ++cnt;
            }
        }
    }

    cout << cnt;
    return 0;
}

关键代码讲解

1. 读取网格

cin >> ch;
if (ch != '0') b[i][j] = true;

用 char 逐字符读取，只将非 '0' 的格子标记为 true（属于细胞）。

2. DFS 递归填充

void dfs(int x, int y) {
    if (!b[x][y]) return;    // 已访问或非细胞 → 返回
    b[x][y] = false;         // 标记为已访问
    dfs(x - 1, y);           // 上
    dfs(x + 1, y);           // 下
    dfs(x, y - 1);           // 左
    dfs(x, y + 1);           // 右
}

递归向四个方向扩散，将整个连通块全部标记为 false，实现 Flood Fill。

3. 计数

if (b[i][j]) {
    dfs(i, j);
    ++cnt;
}

遍历中发现 b[i][j] == true 的格子，说明遇到了一个新的未访问细胞，启动 DFS 填充后计数加一。

复杂度分析

方法	时间复杂度	空间复杂度
Flood Fill	`O(N × M)`，每个格子最多被访问一次	`O(N × M)`（`b` 数组）

易错点

dfs 中必须显式判断边界：x < 0 || y < 0 || x > n || y > m，不能只判断 !b[x][y]。当递归向边缘扩散时，dfs(-1, y) / dfs(x, -1) 会触发数组越界异常（C++ 用固定大小数组恰好物理地址有效，Python/Java 则直接 RE）。
b[x][y] = false 的时机：在递归调用之前标记为已访问，防止同一格子被重复入栈导致死循环。
下标从 1 开始：主循环从 i=1..n、j=1..m 遍历，保证所有递归起点合法。

其他语言解法

Python

import sys
sys.setrecursionlimit(100000)

def dfs(x: int, y: int) -> None:
    """将 (x,y) 所在连通块标记为已访问"""
    if x < 0 or y < 0 or x > n or y > m or not b[x][y]:
        return
    b[x][y] = False
    dfs(x - 1, y)
    dfs(x + 1, y)
    dfs(x, y - 1)
    dfs(x, y + 1)


if __name__ == "__main__":
    n, m = map(int, sys.stdin.readline().split())
    b = [[False] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        line = sys.stdin.readline().strip()
        for j, ch in enumerate(line, start=1):
            if ch != '0':
                b[i][j] = True

    cnt = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if b[i][j]:
                dfs(i, j)
                cnt += 1

    print(cnt)

JavaScript

'use strict';

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split(/\s+/);
const it = input[Symbol.iterator]();
const next = () => it.next().value;

const n = parseInt(next(), 10);
const m = parseInt(next(), 10);

const b = Array.from({ length: n + 1 }, () => Array(m + 1).fill(false));

for (let i = 1; i <= n; ++i) {
    const line = next();
    for (let j = 1; j <= m; ++j) {
        if (line[j - 1] !== '0') {
            b[i][j] = true;
        }
    }
}

function dfs(x, y) {
    if (!b[x] || !b[x][y] || !b[x][y]) return;
    b[x][y] = false;
    dfs(x - 1, y);
    dfs(x + 1, y);
    dfs(x, y - 1);
    dfs(x, y + 1);
}

let cnt = 0;
for (let i = 1; i <= n; ++i) {
    for (let j = 1; j <= m; ++j) {
        if (b[i][j]) {
            dfs(i, j);
            ++cnt;
        }
    }
}

process.stdout.write(String(cnt));

Go

package main

import (
    "bufio"
    "fmt"
    "os"
)

var n, m, cnt int
var b [110][110]bool

func dfs(x, y int) {
    if !b[x][y] {
        return
    }
    b[x][y] = false
    dfs(x-1, y)
    dfs(x+1, y)
    dfs(x, y-1)
    dfs(x, y+1)
}

func main() {
    in := bufio.NewReader(os.Stdin)
    fmt.Fscan(in, &n, &m)

    for i := 1; i <= n; i++ {
        var line string
        fmt.Fscan(in, &line)
        for j, ch := range line {
            if ch != '0' {
                b[i][j+1] = true
            }
        }
    }

    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if b[i][j] {
                dfs(i, j)
                cnt++
            }
        }
    }

    fmt.Println(cnt)
}

Java

import java.io.*;

public class Main {

    static int n, m, cnt;
    static boolean[][] b;

    static void dfs(int x, int y) {
        if (x < 0 || y < 0 || x > n || y > m || !b[x][y]) return;
        b[x][y] = false;
        dfs(x - 1, y);
        dfs(x + 1, y);
        dfs(x, y - 1);
        dfs(x, y + 1);
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        n = fs.nextInt();
        m = fs.nextInt();

        b = new boolean[n + 1][m + 1];

        for (int i = 1; i <= n; ++i) {
            String line = fs.next();
            for (int j = 1; j <= m; ++j) {
                char ch = line.charAt(j - 1);
                if (ch != '0') b[i][j] = true;
            }
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (b[i][j]) {
                    dfs(i, j);
                    ++cnt;
                }
            }
        }

        System.out.println(cnt);
    }

    // FastScanner（避免 Scanner MLE）
    static class FastScanner {
        private final BufferedInputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) {
            in = new BufferedInputStream(is);
        }

        private int readByte() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        String next() throws IOException {
            int c;
            do { c = readByte(); } while (c <= ' ' && c != -1);
            StringBuilder sb = new StringBuilder();
            while (c > ' ') {
                sb.append((char) c);
                c = readByte();
            }
            return sb.toString();
        }

        int nextInt() throws IOException {
            int c, sign = 1, val = 0;
            do { c = readByte(); } while (c <= ' ' && c != -1);
            if (c == '-') { sign = -1; c = readByte(); }
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = readByte();
            }
            return val * sign;
        }
    }
}