寻找矩阵中“块“的个数（BFS）

题目描述

给出一个mxn的矩阵，矩阵中的元素为0或1。称位置（x,y)与其上下左右四个位置(x,y+1)、(x,y-1)、（x+1,y)、(x-1,y)是相邻的。如果矩阵中有若干个1是相邻的（不必两两相邻），那么称这些1构成了一个“块”。求给定的矩阵中“块”的个数。

【输入样例】

6 7
0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0

【输出样例】

4

解题思路

用广度优先搜索来遍历一个“块”，并将其标记为1，标记后就不会再被遍历了，一共遍历几次，就代表有几个“块”。

代码实现

import java.util.*;

public class Main {
    
    //增量
    static int n;
    static int m;
    static int[] X={
    0,0,-1,1};//上 下 左 右
    static int[] Y={
    -1,1,0,0};//上 下 左 右
    static int[][] matrix;//矩阵
    static boolean[][] visted;//用于标记某点是否被访问
    public static void main(String[] args) {
    
        Scanner scan=new Scanner(System.in);
        n=scan.nextInt();//n行
        m= scan.nextInt();//m列
        visted=new boolean[n][m];
        matrix=new int[n][m];
        //输入矩阵
        for (int i = 0; i < n; i++) {
    
            for (int j = 0; j < m; j++) {
    
                matrix[i][j]= scan.nextInt();
            }
        }
        //依次搜索矩阵中的每个点（当然条件是之前没有被搜索过，且该位为0）
        int count=0;
        for (int x = 0; x < n; x++) {
    
            for (int y = 0; y < m; y++) {
    
                if(!visted[x][y]&&matrix[x][y]==1){
    
                    bfs(x,y);  //本题中bfs的结果是，下一个遇到的“1块”被标记为已访问
                    count++;
                }
            }
        }
        System.out.println(count);
        scan.close();
    }
    public static void bfs(int x,int y){
    
        node start=new node(x,y);
        visted[x][y]=true;
        Deque<node> que=new LinkedList<>();
        que.offer(start);
        while(!que.isEmpty()){
    
              node now=que.poll();
              for(int i=0;i<4;i++){
    
                  int newx=now.x+X[i];
                  int newy=now.y+Y[i];
                  if(check(newx,newy)){
    
                      visted[newx][newy]=true;
                      node next=new node(newx,newy);
                      que.offer(next);
                  }
              }
        }
    }
    public static boolean check(int x,int y){
    
        //数组越界
        if(x<0||x>=n||y<0||y>=m){
    
            return false;
        }
        //已经被访问过了
        if(visted[x][y]||matrix[x][y]==0){
    
            return false;
        }
        return true;
    }
}
class node{
    
    int x;
    int y;
    node(){
    }
    node(int x,int y){
    
        this.x=x;
        this.y=y;
    }
}