leetcode刷题笔记 二百题 岛屿数量

leetcode刷题笔记 二百题 岛屿数量

源地址：200. 岛屿数量

问题描述：

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1
示例 2:

输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

//本题可以通过深度优先遍历和宽度优先遍历两种方法
//核心思想是遍历二维数组的1，计数加1，通过深优或宽优将湖内所有的1置0
//深度优先遍历处理
object Solution {
    def numIslands(grid: Array[Array[Char]]): Int = {
       if (grid == null || grid.length == 0)  return 0
       val rowLength = grid.length
       val colLength = grid(0).length
       var count = 0

       def dfs(grid: Array[Array[Char]], row: Int, col: Int): Unit = {
           if (row < 0 || col < 0 || row >= rowLength || col >= colLength || grid(row)(col) == '0') return
           grid(row)(col) = '0'
           dfs(grid, row-1, col)
           dfs(grid, row+1, col)
           dfs(grid, row, col-1)
           dfs(grid, row, col+1)
       }

       for(i <- 0 to rowLength-1){
           for(j <- 0 to colLength-1){
               if (grid(i)(j) == '1'){
                   count += 1
                   dfs(grid, i, j)
               }
           }
       }

       return count
    }
}

//宽度优先遍历处理湖
import scala.collection.mutable
object Solution {
    def numIslands(grid: Array[Array[Char]]): Int = {
        if (grid == null || grid.length == 0) return 0
        val rowLength = grid.length
        val colLength = grid(0).length
        var count = 0

        for(i <- 0 to rowLength-1){
            for(j <- 0 to colLength-1){
                if (grid(i)(j) == '1'){
                    count += 1
                    val queue = new mutable.Queue[(Int, Int)]()
                    queue.enqueue((i, j))
                    grid(i)(j) = '0'
                    while (queue.nonEmpty) {
                        val (row, col) = queue.dequeue
                        if (row+1 < rowLength && grid(row+1)(col) == '1') {
                            queue.enqueue((row+1, col))
                            grid(row+1)(col) = '0'
                        }
                        if (row-1 >= 0 && grid(row-1)(col) == '1') {
                            queue.enqueue((row-1, col))
                            grid(row-1)(col) = '0'
                        }
                        if (col+1 < colLength && grid(row)(col+1) == '1') {
                            queue.enqueue((row, col+1))
                            grid(row)(col+1) = '0'
                        }
                        if (col-1 >= 0 && grid(row)(col-1) == '1') {
                            queue.enqueue((row, col-1))
                            grid(row)(col-1) = '0'
                        }
                    }
                }
            }
        }

        return count
    }
}