leetcode 16.19 水域大小

leetcode 16.19 水域大小

你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。

示例：

输入：
[
[0,2,1,0],
[0,1,0,1],
[1,1,0,1],
[0,1,0,1]
]
输出： [1,2,4]
提示：

0 < len(land) <= 1000
0 < len(land[i]) <= 1000

一般来说这种题用BFS会更快

DFS

class Solution {int[][] land;int num;public int[] pondSizes(int[][] land) {this.land=land;List<Integer> temp=new ArrayList<>();for(int i=0;i<land.length;i++){for(int j=0;j<land[0].length;j++){if(land[i][j]==0){dfs(i,j);temp.add(num);num=0;}}}int[] ans=new int[temp.size()];for(int i=0;i<ans.length;i++) ans[i]&#(i);Arrays.sort(ans);return ans; }public void dfs(int i,int j){if(i<0 || j<0 ||i>=land.length || j>=land[0].length ||land[i][j]!=0){return ;}num++;land[i][j]=-1;dfs(i,j+1);dfs(i,j-1);dfs(i+1,j);dfs(i-1,j);dfs(i-1,j+1);dfs(i-1,j-1);dfs(i+1,j+1);dfs(i+1,j-1);}
}

DFS

class Solution {int[][] land;public int[] pondSizes(int[][] land) {this.land=land;List<Integer> temp=new ArrayList<>();for(int i=0;i<land.length;i++){for(int j=0;j<land[0].length;j++){if(land[i][j]==0){temp.add(dfs(i,j));}}}int[] ans=new int[temp.size()];for(int i=0;i<ans.length;i++) ans[i]&#(i);Arrays.sort(ans);return ans; }public int dfs(int i,int j){if(i<0 || j<0 ||i>=land.length || j>=land[0].length ||land[i][j]!=0){return 0;}land[i][j]=-1;int a=dfs(i,j+1);int b=dfs(i,j-1);int c=dfs(i+1,j);int d=dfs(i-1,j);int e=dfs(i-1,j+1);int f=dfs(i-1,j-1);int g=dfs(i+1,j+1);int h=dfs(i+1,j-1);return 1+a+b+c+d+e+f+g+h;}
}

BFS

class Solution {int[][] land;int[] x_size={0,0,1,-1,-1,-1,1,1};int[] y_size={1,-1,0,0,1,-1,1,-1};public int[] pondSizes(int[][] land) {this.land=land;List<Integer> temp=new ArrayList<>();for(int i=0;i<land.length;i++){for(int j=0;j<land[0].length;j++){if(land[i][j]==0){temp.add(bfs(i,j));}}}int[] ans=new int[temp.size()];for(int i=0;i<ans.length;i++) ans[i]&#(i);Arrays.sort(ans);return ans; }public int bfs(int i,int j){Queue<Integer> queue1=new LinkedList<>();Queue<Integer> queue2=new LinkedList<>();queue1.add(i);queue2.add(j);land[i][j]=-1;int num=1;while(!queue1.isEmpty()){int x=queue1.poll();int y=queue2.poll();for(int k=0;k<=7;k++){int xx=x+x_size[k];int yy=y+y_size[k];if(xx>=0 && yy>=0 && xx<land.length && yy<land[0].length && land[xx][yy]==0){queue1.add(xx);queue2.add(yy);land[xx][yy]=-1;num++;}}}return num;}}