Count Outer Islands

You are given an \(M\times N\) grid map, where each cell is either '0' (representing sea) or '1' (representing land). An island is defined as a maximal group of connected '1's (connections are only considered in the four directions: up, down, left, right). The grid is surrounded by sea.

In an island \(A\), if one can select \(k\) distinct cells \((x_{0},y_{0}), (x_{1},y_{1}), \dots, (x_{k-1},y_{k-1})\) from \(A\)'s cells such that they form a cycle, i.e. for every \(0\le i\le k-1\), the cell \((x_{(i+1)\bmod k}, y_{(i+1)\bmod k})\) is exactly one move (up/down/left/right) away from \((x_i, y_i)\), then these \(k\) cells form a "ring."

If every cell of another island \(B\) lies strictly inside one such ring of island \(A\), then \(B\) is called a sub‐island of \(A\). Note that the sub‐island relation is transitive: if \(B\) is a sub‐island of \(A\) and \(C\) is a sub‐island of \(B\), then \(C\) is also a sub‐island of \(A\).

Your task is to count the number of islands on the map excluding those islands that are sub‐islands of another island.

Note: An island \(A\) can only enclose another island if and only if it contains at least one cycle (ring) as described above. For the purpose of checking the containment, treat each grid cell as a unit square and use its center point \((x+0.5, y+0.5)\) for geometric computations. Use the standard ray‐casting method to test if a point lies inside a polygon.

inputFormat

The first line contains two integers \(M\) and \(N\) \((1 \le M, N \le 1000)\), representing the number of rows and columns of the grid respectively.

Each of the next \(M\) lines contains a string of length \(N\) consisting only of characters '0' and '1'.

outputFormat

Output a single integer: the number of islands that are not sub‐islands of any other island.

sample

3 3
010
111
010

1