LeetCode 水域大小

1.题目

2.思路

经典的DFS+回溯法套路模板,这题比较麻烦的是需要遍历 8 个方向
Java语言题解

class Solution {List<Integer> array = new ArrayList<Integer>();int rowLen;int colLen;public int[] pondSizes(int[][] land) {rowLen = land.length;colLen = land[0].length;for(int i = 0;i<rowLen;i++){for(int j = 0;j<colLen;j++){if(land[i][j] == 0){array.add(dfs(land,i,j));land[i][j] = 0;}}}Collections.sort(array);int size = array.size();int[] result = new int[size];for(int i = 0;i<size;i++){result[i] = array.get(i).intValue();}return result;}public int dfs(int[][] land,int i,int j){if(!checkBoard(land,i,j)){return 0;}int count = 1;land[i][j] = -1;count+=dfs(land,i-1,j-1); // 左上角count+=dfs(land,i-1,j); //正上方count+=dfs(land,i-1,j+1); //右上角count+=dfs(land,i,j+1); //右一个count+=dfs(land,i+1,j+1); //右下角count+=dfs(land,i+1,j); //正下方count+=dfs(land,i+1,j-1);//左下角count+=dfs(land,i,j-1); //左一个return count;}public boolean checkBoard(int[][] land,int i,int j){if(i>=rowLen || i<0) return false;if(j>=colLen || j<0) return false;return land[i][j] == 0;}}

3.总结

不要忘记回溯,DFS过程中做的标记需要记得还原,否则会栈溢出