给定一个 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);
}
}