463. 岛屿的周长

àì夳堔傛蜴生んèń 2023-07-20 13:33 40阅读 0赞

# 题目： #

[463. 岛屿的周长][463.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解： #

## 1. 题解一：直接遍历 ##

直接遍历数组，只要前面有相邻的方格，就-2。  
因为方格A和方格B相邻，方格A，B需要分别减少一条边。

## 2. 题解二：DFS（首选） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]

# 代码： #

## 1. 代码一：直接遍历 ##

/** * code463 */
    public class code463 { 
    
    
        public static int islandPerimeter(int[][] grid) { 
            // 重点关注前面遍历过得方格，如果之前有相邻方格，就-2;
            if(grid.length == 0)
            { 
                return 0;
            }
            int length = 0;
            int m = grid.length;
            int n = grid[0].length;
            for(int i = 0; i < m; i++)
            { 
                for(int j = 0; j < n; j++)
                { 
                    if(grid[i][j] == 1)
                    { 
                        length += 4;
                        // 如果grid[i-1][j]不小于数组边界并且也等于1（岛）则边减2
                        if(i > 0 && grid[i - 1][j] == 1)
                        { 
                            length -= 2;
                        }
                        // 如果grid[i][j-1]不小于数组边界并且也等于1（岛）则边减2
                        if(j > 0 && grid[i][j - 1] == 1)
                        { 
                            length -= 2;
                        }
                    }
                }
            }
            return length;
        }
    
        public static void main(String[] args) { 
            int grid[][] = { 
                { 0, 1, 0, 0},
                { 1, 1, 1, 0},
                { 0, 1, 0, 0},
                { 1, 1, 0, 0}
            };
            int res = islandPerimeter(grid);
            System.out.println(res);
        }
    }

## 2. 代码二：DFS（首选） ##

/** * code463 */
    public class code463 { 
    
        public static int islandPerimeter(int[][] grid) { 
            if(grid.length == 0)
            { 
                return 0;
            }
            int m = grid.length;
            int n = grid[0].length;
            boolean visited[][] = new boolean[m][n];
            for(int i = 0; i < m; i++)
            { 
                for(int j = 0; j < n; j++)
                { 
                    if(grid[i][j] == 1)
                    { 
                        // 题目限制只有一个岛屿,计算一个岛屿即可,即找到一个岛屿后立刻返回即可
                        return dfs(i, j, m, n, grid, visited);
                    }
                }
            }
            return 0;
        }
    
        public static int dfs(int i, int j, int m, int n, int grid[][], boolean visited[][])
        { 
            // 从一个岛屿方格走向网格边界，周长加 1
            if(i < 0 || i >= m || j < 0 || j >= n)
            { 
                return 1;
            }
            // 从一个岛屿方格走向水域方格，周长加 1
            if(grid[i][j] == 0)
            { 
                return 1;
            }
            if(visited[i][j])
            { 
                return 0;
            }
            //标记访问
            visited[i][j] = true;
            return dfs(i + 1, j, m, n, grid, visited) + dfs(i - 1, j, m, n, grid, visited) + dfs(i, j + 1, m, n, grid, visited) + dfs(i, j - 1, m, n, grid, visited);
        }
    
        public static void main(String[] args) { 
            int grid[][] = { 
                { 0, 1, 0, 0},
                { 1, 1, 1, 0},
                { 0, 1, 0, 0},
                { 1, 1, 0, 0}
            };
            int res = islandPerimeter(grid);
            System.out.println(res);
        }
    }

# 参考： #

1.  [图解：在 DFS 遍历过程中求周长（Java）][DFS _Java]
2.  [岛屿的周长][Link 1]

[463.]: https://leetcode-cn.com/problems/island-perimeter/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: /images/20230528/0ab1d27e31aa413b8cb474018ae1640f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/7c72a9bed12940ecb8fe39e189f9f14a.png
[DFS _Java]: https://leetcode-cn.com/problems/island-perimeter/solution/tu-jie-jian-ji-er-qiao-miao-de-dfs-fang-fa-java-by/
[Link 1]: https://leetcode-cn.com/problems/island-perimeter/solution/dao-yu-de-zhou-chang-by-liang-jian-sheng-cun/