目录
岛屿数量
访问量:409

一、简介

给一个01矩阵,1代表是陆地,0代表海洋, 如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

岛屿: 相邻陆地可以组成一个岛屿(相邻:上下左右) 判断岛屿个数。

例如:

输入

[

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

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

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

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

[0,0,1,1,1]

]

对应的输出为3


二、实现

思路:遍历二维数组中的元素,

  1. 若为陆地,岛屿数量+1,则将当前位置添加到栈中

  2. 遍历栈,取出位置s1,将s1设置为海洋,代表已遍历过

  3. 判断位置s1上下左右,若存在陆地,则加入栈中

  4. 执行第二步,直到栈为空

type Stack struct {
   data []*StackNode
}

type StackNode struct {
   col int
   row int
}

func (s *Stack) add(d *StackNode) {
   if len(s.data) == 0 {
      s.data = make([]*StackNode, 0)
   }

   s.data  = append(s.data , d)
}

func (s *Stack) pop() *StackNode {
   if len(s.data) == 0 {
      return nil
   }

   curVal := s.data[0]

   s.data = s.data[1:]

   return curVal
}

func (s *Stack) len() int {
   return len(s.data)
}

/**
 * 判断岛屿数量
 * @param grid char字符型二维数组
 * @return int整型
 */
func solve( grid [][]byte ) int {
   // write code here
   num :=0

   for i:=0; i< len(grid); i++ {
      for j:=0; j < len(grid[i]); j++ {
         if grid[i][j] == 0 {
            continue
         }

         num ++

         // 将 grid[i][j] 相邻的企且为 1的节点设置为0
         stack := new(Stack)
         stack.add(&StackNode{
            col:i,
            row:j,
         })

         for stack.len() > 0 {
            curNode := stack.pop()

            grid[curNode.col][curNode.row] = 0

            // 判断是否有左节点,且 == 1
            if curNode.row > 0  && grid[curNode.col][curNode.row -1] == 1{
               stack.add(&StackNode{
                  col:curNode.col,
                  row:curNode.row -1,
               })
            }

            // 判断是否有右节点,且 == 1
            if curNode.row  < (len(grid[curNode.col]) -1)  && grid[curNode.col][curNode.row+1] == 1{
               stack.add(&StackNode{
                  col:curNode.col,
                  row:curNode.row +1,
               })
            }

            // 判断其上方节点,是否等于1
            if curNode.col > 0 && grid[curNode.col -1][curNode.row] == 1 {
               stack.add(&StackNode{
                  col:curNode.col -1,
                  row:curNode.row,
               })
            }

            // 判断其下方是否有节点
            if curNode.col < (len(grid) - 1) && grid[curNode.col +1][curNode.row] == 1 {
               stack.add(&StackNode{
                  col:curNode.col +1,
                  row:curNode.row,
               })
            }
         }

      }
   }

   return num
}