package arrays;

/**题目:小岛数量
 * y:
 * 1 0 0
 * 0 1 1
 * 0 1 1
 *
 * 小岛数量为2(一个1或者连通起来都是1的都计数为一个小岛,0表示海水)
 * @Author Gavin
 * @date 2022年01月11日 22:26
 */
public class array_15 {
 /**
 * 解题思路:
 * 暴力破解法,定义一个相同的二维数组用于存储是否被访问,然后遍历数组,
 * 遇到0就直接返回,如果遇到1就让小岛数量加1,并且把该值的上下左右都是1的标记
 * 为已经访问的,这样就让再次访问到旁边的1就不会增加小岛数量值
 */
 //定义一个递归函数,作用就是把小岛周围的标记为是否已经访问
 private void help(char[][] g,boolean[][] visit,int i,int j){
 int m=g.length,n=g[0].length;
 //核心判断逻辑
 if(i<0||i>=m||j<0||j>=n||g[i][j]=='0'||visit[i][j])return;

 visit[i][j]=true;
 //就是把元素的上下左右如果都是1的话都标记为已经访问状态(i是上下,j是左右)
 help(g,visit,i-1,j);
 help(g,visit,i+1,j);
 help(g,visit,i,j-1);
 help(g,visit,i,j+1);
 }
 //Time:O(m*n) Space:O(m*n)
 public int solution(char[][] g){
 if(g==null||g.length==0||
 g[0]==null||g[0].length==0)return 0;

 int m=g.length,n=g[0].length;
 boolean[][] visit=new boolean[m][n];
 int num=0;

 for (int i = 0; i < m; i++) {
 for (int j = 0; j < n; j++) {
 if(g[i][j]=='0'||visit[i][j])continue;
 ++num;
 help(g,visit,i,j);
 }
 }
 return num;
 }

 public static void main(String[] args) {
 int[][] a=new int[][]{{1,2},{3,4},{5,6}};
 System.out.println(a.length);
 }
}