leetcode 水域大小（DFS）

admin管理员组

文章数量:1516870

leetcode 水域大小（DFS）

题目

思路及代码

1、全通过代码

与其他DFS题不同的地方：

1、递归开始调用的地方，每个0统计后就不能再次进行统计了，所以在主方法进行调用的地方要先判断flag是否为false，保证该位置没有被统计到水域中；

2、对输出进行排序（题目要求）；

3、边界值问题

   主方法调用处： i< length  或i<= length-1;

    递归处：不能取到的临界值，比如length不能取到，所以等于也不行。

import java.util.ArrayList;
import java.util.Collections;
class Solution {public int[] pondSizes(int[][] land) {// 垂直 i+-1,j    水平 i,j+-1     //对角  左上 i-1,j-1  左下 i-1,j+1   右上 i+1,j-1  右下   i+1,j+1ArrayList<Integer> save = new ArrayList<>();int rows= land.length;int cols = land[0].length; boolean [][] flag = new boolean [rows][cols];for(int i= 0;i<rows;i++){for(int j = 0;j< cols;j++){if(land[i][j]== 0 && flag[i][j] == false){save.add(search(land,flag,rows,cols,i,j));}}}Collections.sort(save);int len = save.size();int [] size = new int [len];for(int i = 0;i<len;i++){size[i] = save.get(i);}return size;}public int search (int [][] land,boolean [][] flag,int rows,int cols,int i,int j){if(i<0 || i>= rows || j<0 || j>= cols|| flag[i][j] == true || land [i][j] !=0){return 0;}flag[i][j] = true;return(1+ search(land,flag,rows,cols,i-1,j)+//上search(land,flag,rows,cols,i+1,j)+//下search(land,flag,rows,cols,i,j-1)+search(land,flag,rows,cols,i,j+1)+search(land,flag,rows,cols,i-1,j-1)+search(land,flag,rows,cols,i-1,j+1)+search(land,flag,rows,cols,i+1,j-1)+search(land,flag,rows,cols,i+1,j+1));}
}

import java.util.ArrayList;
class Solution {public int[] pondSizes(int[][] land) {// 垂直 i+-1,j    水平 i,j+-1     //对角  左上 i-1,j-1  左下 i-1,j+1   右上 i-1,j-1  右下   i+1,j+1ArrayList<Integer> save = new ArrayList<>();int rows= land.length-1;int cols = land[0].length-1; boolean [][] flag = new boolean [rows][cols];for(int i= 0;i< rows;i++){for(int j = 0;j< cols;j++){if(land[i][j]== 0){save.add(search(land,flag,rows,cols,i,j));}}}int len = save.size();int [] size = new int [len];for(int i = 0;i<len;i++){size[i] = save.get(i);}return size;}public int search (int [][] land,boolean [][] flag,int rows,int cols,int i,int j){if(i<0 || i>= rows || j<0 ||j>= cols|| flag[i][j] == true || land [i][j] !=0){return 0;}flag[i][j] = true;return(1+ search(land,flag,rows,cols,i-1,j)+search(land,flag,rows,cols,i+1,j)+search(land,flag,rows,cols,i,j-1)+search(land,flag,rows,cols,i,j+1)+search(land,flag,rows,cols,i-1,j-1)+search(land,flag,rows,cols,i-1,j+1)+search(land,flag,rows,cols,i-1,j-1)+search(land,flag,rows,cols,i+1,j+1));}
}

本文标签： leetcode 水域大小（DFS）