首页 > 代码库 > leetcode 463. Island Perimeter

leetcode 463. Island Perimeter

题目: 以二维数组形式表示坐标岛屿,求边长。

例子: 

[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:

技术分享

 

思路:    一开始想用最笨的办法,就是两次for循环遍历所有元素,如果为1(1为岛屿),就分别判断 上、下、左、右 是否为岛屿,若不是则 边数+1 。

          第二次换了想法, 每一条横向 如果有岛屿,只要连续,那么左右两边和始终为2,如果不连续,则左右两边和 +2。  纵向判断 上下边 也是如此。

   所用tag记录上一格是否为岛屿 来判断是否连续,如果为连续,则这一横排的 左右边和 始终为2, 如果有一个不连续,则左右边和 +2 。 

     横向判断用两次for循环,纵向判断也用两次for循环。第二层循环之前要把 tag清空,否则上一行的最后一格 和 下一行的第一格 会误判。

   

   效率一般,更好的没想起来- -

 1 public class Solution {
 2     public int islandPerimeter(int[][] grid) {
 3         int m = 0,tag = 0; //m记录边数 ,tag作为标记 记录是否为连续岛屿
 4         int rows = grid.length;   
 5         int columns = grid[0].length;
 6         for(int i = 0;i < rows;i++){   //横向遍历
 7             tag = 0 ;   //下层循环 标记清零
 8             for(int j = 0; j < columns; j++){
 9                 if(grid[i][j] == 1){
10                     if(tag == 1){
11                         continue;
12                     }
13                     m = m + 2;
14                     tag = 1;
15                 }
16                 else{
17                     tag = 0;
18                 }
19             }
20         }
21         for(int j = 0; j < columns; j++){  //纵向遍历
22             tag = 0; //下层循环  标记清零
23             for(int i = 0;i < rows;i++){
24                 if(grid[i][j] == 1){
25                     if(tag == 1){
26                         continue;
27                     }
28                     m = m + 2;
29                     tag = 1;
30                 }
31                 else{
32                     tag = 0;
33                 }
34             }
35         }
36         
37         return m;
38     }
39 }

 

leetcode 463. Island Perimeter