开心消消乐

 给定一个 N 行 M 列的二维矩阵,矩阵中每个位置的数字取值为 0 或 1,矩阵示例如:

1 1 0 0
0 0 0 1 
0 0 1 1 
1 1 1 1 

 现需要将矩阵中所有的 1 进行反转为 0,规则如下:
  1. 当点击一个 1 时,该 1 被反转为 0,同时相邻的上、下、左、右,以及左上、左下、右上、右下 8 个方向的 1 (如果存在 1)均会自动反转为 0;
  2. 进一步地,一个位置上的 1 被反转为 0 时,与其相邻的 8 个方向的 1 (如果存在 1)均会自动反转为 0。
 按照上述规则示例中的矩阵只最少需要点击 2 次后,所有均值 0 。
 请问,给定一个矩阵,最少需要点击几次后,所有数字均为 0?
 输入描述:
  第一行输入两个整数,分别表示矩阵的行数 N 和列数 M,取值范围均为 [1,100]
  接下来 N 行表示矩阵的初始值,每行均为 M 个数,取值范围 [0,1]
 输出描述:
  输出一个整数,表示最少需要点击的次数

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int col = sc.nextInt();
        int row = sc.nextInt();
        int[][] pointArray = new int[col][row];
        for(int i = 0;i < col;i++){
            for(int j = 0;j < row;j++){
                pointArray[i][j] = sc.nextInt();
            }
        }
        
        int step = 0;
        for(int i = 0;i < col;i++){
            for(int j = 0;j < row;j++){
                if(pointArray[i][j] == 1){
                    step++;
                    dfs(pointArray,col,row,i,j);
                }
            }
        }
        System.out.print(step);
    }
    
    public static void dfs(int[][] pointArray,int col,int row,int i,int j){
        if(i < 0||j < 0||i >= col||j >= row||pointArray[i][j] == 0){
            return;
        }
        pointArray[i][j] = 0;
        dfs(pointArray,col,row,i-1,j);
        dfs(pointArray,col,row,i+1,j);
        dfs(pointArray,col,row,i,j-1);
        dfs(pointArray,col,row,i,j+1);
        dfs(pointArray,col,row,i-1,j-1);
        dfs(pointArray,col,row,i-1,j+1);
        dfs(pointArray,col,row,i+1,j+1);
        dfs(pointArray,col,row,i+1,j-1);
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容