Count Closed Islands

Given an \(n \times n\) grid where each cell contains either a 0 or a 1, your task is to count the number of closed islands. In this problem, a closed island is defined as a group of adjacent cells with value 0 that is completely surrounded by cells with value 1. A cell is considered adjacent to another if they are horizontally or vertically neighboring.

Formally, let \(G\) be the grid and \(0 \le i, j < n\) be its indices. A cell \(G(i, j) = 0\) is part of a closed island if and only if, when performing a depth-first search (DFS) (or breadth-first search) from \(G(i, j)\), none of the cells in the connected component reaches the boundary of the grid. Equivalently, an island is closed if for every cell in the island, all four neighbors (if they exist) are either part of the island or are 1 (water).

Your program should read the input from stdin and output the result to stdout.

inputFormat

The input begins with an integer \(n\) denoting the size of the grid. The next \(n\) lines each contain \(n\) space-separated integers (each either 0 or 1) representing the grid. Here, 0 represents land and 1 represents water.

Note: A closed island is formed by cells with value 0 that do not touch the border of the grid.

outputFormat

Output a single integer representing the number of closed islands in the grid.

3
0 0 0
0 0 0
0 0 0

0