LeetCode图相关知识-floodfill算法
发布时间
阅读量：
阅读量
floodfill算法
二维数组转成一位数组
一维数组转二维数组
二维数组的四连通
int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};#控制方向左右上下
访问arr元素周围的左右下上周围四个方向的元素。
二维数组的八连通
int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}{-1,-1},{-1,1},{1,-1},{1,1}};
#控制方向左，右，上，下,左上，左下，右上，右下
保证索引
if 中的判断可以保证我们计算出来的row和col是在合法的区间内补。
经典leetcode岛屿的数量
public class MaxAreaOfIsland1 {
private int rows;
private int cols;
private int[][] grid;
private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int maxAreaOfIsland(int[][] grid) {
if (grid == null) return 0;
rows = grid.length;
if (rows == 0) return 0;
cols = grid[0].length;
if (cols == 0) return 0;
this.grid = grid;
int res = 0;
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (grid[row][col] == 1) {
res = Math.max(dfs(row, col), res);
}
}
}
return res;
}
private int dfs(int row, int col) {
grid[row][col] = 0;
int res = 1;
for (int[] dir : directions) {
int nextRow = row + dir[0];
int nextCol = col + dir[1];
if (inArea(nextRow, nextCol)
&& grid[nextRow][nextCol] == 1) {
res += dfs(nextRow, nextCol);
}
}
return res;
}
private boolean inArea(int row, int col) {
return row >= 0 && row < rows && col >= 0 && col < cols;
}
public static void main(String[] args) {
int[][] grid = {
{0,0,1,0,0,0,0,1,0,0,0,0,0},
{0,0,1,0,0,0,0,1,1,1,0,0,0},
{0,1,0,0,1,0,0,0,0,0,0,0,0},
{0,1,0,0,1,1,0,0,1,0,1,0,0},
{0,1,0,0,1,1,0,0,1,1,1,0,0},
{0,0,1,0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,1,1,1,0,0,0},
{0,0,0,0,0,0,0,1,1,0,0,0,0},
};
MaxAreaOfIsland1 maxAreaOfIsland = new MaxAreaOfIsland1();
System.out.println(maxAreaOfIsland.maxAreaOfIsland(grid));
}
}
全部评论 (0)
还没有任何评论哟~