463.island-perimeter.md

463. Island Perimeter

Test Cases

Normal Cases

• One case that covers all the possible scenarios.

Input: [[0,1,0,0],
        [1,1,1,0],
        [0,1,0,0],
        [1,1,1,0]]

Iteration

For each land cell, we check the four directions to see if it is a boundary or water cell. If it is a boundary or water cell, we increment the perimeter by 1.

water? or out of boundary?
           |
...  --- land --- ...
           |
          ...

fun islandPerimeter(grid: Array<IntArray>): Int {
    var perimeter = 0
    val m = grid.size
    val n = grid[0].size
    for (x in 0 until m) {
        for (y in 0 until n) {
            if (grid[x][y] == 1) {
                for (d in directions) {
                    val newX = x + d[0]
                    val newY = y + d[1]
                    if (newX !in 0 until m || newY !in 0 until n) perimeter++
                    else if (grid[newX][newY] == 0) perimeter++
                }
            }
        }
    }
    return perimeter
}

• Time Complexity: O(m * n).
• Space Complexity: O(1).

Traversal

We can start from the first cell with value 1 and traverse the graph to find the perimeter of the island. For every cell, the total perimeter of the current cell is tht sum of the perimeter of the current cell and the perimeter of the adjacent cells, perimeter(current) = perimeter(up) + perimeter(left) + perimeter(right) + perimeter(down).

                  perimeter(up)
                        |
perimeter(left) - perimeter(current) - perimeter(right)
                        |
                  perimeter(down)

For single cell, it might be:

• Out of boundary: that is considered as connected to water, return 1. (Base case) We can NOT skip this case.
• Wate: return 1. (Base case)
• Visited: return 0. (Base case)
• Land: return the current perimeter + perimeter of the adjacent cells. (Recursive case)

岛屿的周长就是岛屿方格和非岛屿方格相邻的边的数量。注意，这里的非岛屿方格，既包括水域方格，也包括网格的边界。

private val visited = 2

fun islandPerimeter(grid: Array<IntArray>): Int {
    var perimeter = 0
    for (i in 0 until grid.size) {
        for (j in 0 until grid[0].size) {
            if (grid[i][j] == 1)
                perimeter += dfs(grid, i, j)
        }
    }
    return perimeter
}

private fun dfs(grid: Array<IntArray>, x: Int, y: Int): Int {
    val m = grid.size
    val n = grid[0].size
    if (x !in 0 until m || y !in 0 until n) return 1
    if (grid[x][y] == 0) return 1
    if (grid[x][y] == visited) return 0

    grid[x][y] = visited
    var perimeter = 0
    directions.forEach { d -> 
        perimeter += dfs(grid, x + d[0], y + d[1])
    }
    return perimeter
}

// Or equivalently, we check before we invoke DFS for the adjacent cells.
private fun dfs(grid: Array<IntArray>, x: Int, y: Int): Int {
    val m = grid.size
    val n = grid[0].size

    grid[x][y] = visited
    var perimeter = 0
    directions.forEach { d -> 
        val newX = x + d[0]
        val newY = y + d[1]
        // For the out of boundary or water, we CAN NOT skip!!
        if (newX !in 0 until m || newY !in 0 until n) perimeter++
        else if (grid[newX][newY] == 0) perimeter++
        else if (grid[newX][newY] == 1) perimeter += dfs(grid, newX, newY)
    }
    return perimeter
}

private fun bfs(grid: Array<IntArray>, x: Int, y: Int): Int {
    val queue = ArrayDeque<Pair<Int, Int>>()
    queue.addLast(x to y)
    var perimeter = 0
    while (queue.isNotEmpty()) {
        val (x, y) = queue.removeFirst()

        if (x !in 0 until grid.size || y !in 0 until grid[0].size) perimeter++
        else if (grid[x][y] == 0) perimeter++
        else if (grid[x][y] == visited) continue
        else {
            grid[x][y] = visited
            directions.forEach { d ->
                queue.addLast(x + d[0] to y + d[1])
            }
        }
    }
    return perimeter
}

// Or equivalently, we check before we invoke BFS for the adjacent cells.
private fun bfs(grid: Array<IntArray>, x: Int, y: Int): Int {
    val m = grid.size
    val n = grid[0].size
    val queue = ArrayDeque<Pair<Int, Int>>()
    queue.addLast(x to y)
    grid[x][y] = visited
    var perimeter = 0
    while (queue.isNotEmpty()) {
        val (x, y) = queue.removeFirst()
        for (d in directions) {
            val newX = x + d[0]
            val newY = y + d[1]
            if (newX !in 0 until m || newY !in 0 until n) perimeter++
            else if (grid[newX][newY] == 0) perimeter++
            else if (grid[newX][newY] == 1) {
                queue.addLast(newX to newY)
                grid[newX][newY] = visited
            }
        }
    }
    return perimeter
}

• Time Complexity: O(m * n).
• Space Complexity: O(m * n).