本文共 3471 字，大约阅读时间需要 11 分钟。

给定一个n×m的矩阵，其中每个元素为0或1，目标是找出其中连通的1块的数量。1块的定义是一个连续的区域，其中每个1至少与上下左右中的一个相邻。相邻指的是上下左右四个方向。

思路分析

对于这个问题，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。两种方法的核心思想都是从一个未被访问的1开始，标记所有与之连通的1，并计数连通块的数量。

深度优先搜索（DFS）

• 从矩阵中的一个未被访问的1开始。
• 标记当前位置为已访问。
• 递归访问其四个相邻的1，直到无法继续。
• 每次找到一个新的1块时，计数加1。

广度优先搜索（BFS）

• 使用队列来处理节点。
• 初始化队列，将起始节点加入队列，并标记为已访问。
• 每次从队列中取出一个节点，检查其四个相邻的位置。
• 对于未被访问的1，加入队列并标记为已访问。
• 当队列为空时，当前块的处理完成，计数加1。

代码实现

Java代码

import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class Main {    static int n, m;    static int[][] arr;    static boolean[][] visited;    static int[] posx = {0, 0, 1, -1};    static int[] posy = {1, -1, 0, 0};    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        n = sc.nextInt();        m = sc.nextInt();        arr = new int[n][m];        visited = new boolean[n][m];        for (int i = 0; i < n; i++) {            for (int j = 0; j < m; j++) {                arr[i][j] = sc.nextInt();            }        }        int res = 0;        for (int i = 0; i < n; i++) {            for (int j = 0; j < m; j++) {                if (arr[i][j] == 1 && !visited[i][j]) {                    res++;                    bfs(i, j);                }            }        }        System.out.println(res);        sc.close();    }    private static void bfs(int x, int y) {        Queue
   
     queue = new LinkedList<>();        visited[x][y] = true;        queue.add(new Node(x, y));        while (!queue.isEmpty()) {            Node current = queue.poll();            for (int i = 0; i < 4; i++) {                int newx = current.x + posx[i];                int newy = current.y + posy[i];                if (judge(newx, newy)) {                    Node newNode = new Node(newx, newy);                    visited[newx][newy] = true;                    queue.add(newNode);                }            }        }    }    private static boolean judge(int x, int y) {        if (x < 0 || x >= n || y < 0 || y >= m) {            return false;        }        return arr[x][y] == 1 && !visited[x][y];    }    private static class Node {        int x;        int y;        Node(int x, int y) {            this.x = x;            this.y = y;        }    }}
   

C++代码

#include 
   
    #include 
    
     #include 
     
      using namespace std;struct Node {    int x;    int y;};int main() {    int n, m;    vector
      
       > arr(n, vector
       
        (m, 0));    vector
        
         > visited(n, vector
         
          (m, false)); cin >> n >> m; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { int val; cin >> val; arr[i][j] = val; } } int res = 0; vector
          
            posx = {0, 0, 1, -1}; vector
           
             posy = {1, -1, 0, 0}; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (arr[i][j] == 1 && !visited[i][j]) { res++; queue
            
              q; q.push({i, j}); visited[i][j] = true; while (!q.empty()) { Node current = q.front(); q.pop(); for (int d = 0; d < 4; ++d) { int newx = current.x + posx[d]; int newy = current.y + posy[d]; if (newx >= 0 && newx < n && newy >= 0 && newy < m) { if (arr[newx][newy] == 1 && !visited[newx][newy]) { visited[newx][newy] = true; q.push({newx, newy}); } } } } } } } cout << res << endl; return 0;}
            
           
          
         
        
       
      
     
    
   

代码解释

• 输入处理：读取矩阵的行数和列数，并将矩阵存储在二维数组arr中。
• 遍历矩阵：检查每个位置，如果是1且未被访问过，开始BFS。
• BFS处理：使用队列处理节点，标记所有连通的1，并计数块的数量。
• 判断函数：检查新位置是否在矩阵内且为1且未被访问过。

两种语言的实现都遵循了相同的逻辑，通过BFS高效地找到所有连通块，确保每个块只被计数一次。

转载地址：http://jrwg.baihongyu.com/