LeetCode 463. 岛屿的周长 java题解

https://leetcode.cn/problems/island-perimeter/

方法一

class Solution {public int islandPerimeter(int[][] grid) {int[][] dir={{0,-1},{0,1},{1,0},{-1,0}};//四个方向int m=grid.length;int n=grid[0].length;int res=0;//周长for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){for(int k=0;k<4;k++){int x=i+dir[k][0];int y=j+dir[k][1];if(x<0||y<0||x>=m||y>=n||grid[x][y]==0){//出去就不是陆地了res++;}}}}}return res;}
}

他人答案

// 解法一
class Solution {// 上下左右 4 个方向int[] dirx = {-1, 1, 0, 0};int[] diry = {0, 0, -1, 1};public int islandPerimeter(int[][] grid) {int m = grid.length;int n = grid[0].length;int res = 0; // 岛屿周长for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {for (int k = 0; k < 4; k++) {int x = i + dirx[k];int y = j + diry[k];// 当前位置是陆地，并且从当前位置4个方向扩展的“新位置”是“水域”或“新位置“越界，则会为周长贡献一条边if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {res++;continue;}}}}}return res;}
}// 解法二
class Solution {public int islandPerimeter(int[][] grid) {// 计算岛屿的周长 // 方法二 : 遇到相邻的陆地总周长就-2int landSum = 0; // 陆地数量 int cover = 0; // 相邻陆地数量for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == 1) {landSum++;// 统计上面和左边的相邻陆地if(i - 1 >= 0 && grid[i-1][j] == 1) cover++;if(j - 1 >= 0 && grid[i][j-1] == 1) cover++;// 为什么没统计下边和右边？ 因为避免重复计算}}}return landSum * 4 - cover * 2;}
}
// 延伸 - 傳統DFS解法(使用visited數組)（遇到邊界 或是 海水 就edge ++）
class Solution {int dir[][] ={{0, 1},{0, -1},{1, 0},{-1, 0}};boolean visited[][];int res = 0;public int islandPerimeter(int[][] grid) {int row = grid.length;int col = grid[0].length;visited = new boolean[row][col];int result = 0;for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){if(visited[i][j] == false && grid[i][j] == 1)result += dfs(grid, i, j);}}return result;}private int dfs(int[][] grid, int x, int y){//如果遇到 邊界（x < 0 || y < 0 || x >= grid.length || y >= grid[0].length）或是 遇到海水(grid[x][y] == 0)就return 1（edge + 1）if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0)return 1;//如果該地已經拜訪過，就return 0 避免重複計算if(visited[x][y])return 0;int temp = 0;visited[x][y] = true;for(int i = 0; i < 4; i++){int nextX = x + dir[i][0];int nextY = y + dir[i][1];//用temp 把edge存起來temp +=dfs(grid, nextX, nextY);}return temp;}
}