1254-number-of-closed-islands.rb

# frozen_string_literal: true

# 1254. Number of Closed Islands
# https://leetcode.com/problems/number-of-closed-islands/

=begin

Given a 2D grid consists of 0s (land) and 1s (water).  An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

### Example 1:
Input: grid = [[1,1,1,1,1,1,1,0],
               [1,0,0,0,0,1,1,0],
               [1,0,1,0,1,1,1,0],
               [1,0,0,0,0,1,0,1],
               [1,1,1,1,1,1,1,0]]
Output: 2
Explanation:
Islands in gray are closed because they are completely surrounded by water (group of 1s).

### Example 2:
Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1

### Example 3:

Input: grid = [[1,1,1,1,1,1,1],
               [1,0,0,0,0,0,1],
               [1,0,1,1,1,0,1],
               [1,0,1,0,1,0,1],
               [1,0,1,1,1,0,1],
               [1,0,0,0,0,0,1],
               [1,1,1,1,1,1,1]]
Output: 2

### Constraints:
* 1 <= grid.length, grid[0].length <= 100
* 0 <= grid[i][j] <=1

=end

# @param {Integer[][]} grid
# @return {Integer}
def closed_island(grid)
  (0...grid.size).each do |i|
    (0...grid[i].size).each do |j|
      if i * j == 0 || i == grid.size - 1 || j == grid[i].size - 1
        fill(grid, i, j)
      end
    end
  end

  res = 0

  (0...grid.size).each do |i|
    (0...grid[i].size).each do |j|
      if grid[i][j] == 0
        res += 1
        fill(grid, i, j)
      end
    end
  end

  res
end

def fill(g, x, y)
  if x < 0 || y < 0 || x >= g.size || y >= g[x].size || g[x][y] == 1
    return
  end

  g[x][y] = 1
  directions = [0, 1, 0, -1, 0]
  (0..3).each do |i|
    fill(g, x + directions[i], y + directions[i + 1])
  end
end


# **************** #
#       TEST       #
# **************** #

require "test/unit"
class Test_closed_island < Test::Unit::TestCase
  def test_
    assert_equal 2, closed_island([[1, 1, 1, 1, 1, 1, 1, 0], [1, 0, 0, 0, 0, 1, 1, 0], [1, 0, 1, 0, 1, 1, 1, 0], [1, 0, 0, 0, 0, 1, 0, 1], [1, 1, 1, 1, 1, 1, 1, 0]])
    assert_equal 1, closed_island([[0, 0, 1, 0, 0], [0, 1, 0, 1, 0], [0, 1, 1, 1, 0]])
    assert_equal 2, closed_island([[1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0, 1], [1, 0, 1, 1, 1, 0, 1], [1, 0, 1, 0, 1, 0, 1], [1, 0, 1, 1, 1, 0, 1], [1, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1]])
  end
end