Problem Description

Count the number of islands in a binary matrix where 1 represents land and 0 represents water. Unlike the classic version, lands connected diagonally (8-directional) also form part of the same island.

Input Format

First line contains m and n (matrix dimensions). Next m lines contain n space-separated integers (0 or 1).

Output Format

Single integer representing the number of islands.

Constraints

• 1 ≤ m, n ≤ 100

• Matrix contains only 0s and 1s

• Islands are connected in 8 directions (including diagonals)

• Single land cell counts as one island

Sample Input/Output

4 5
1 1 0 0 0
0 1 0 0 1
1 0 0 1 1
0 0 0 0 0

2

Explanation

Island 1: Connected lands at (0,0), (0,1), (1,1), (2,0) - they are connected through diagonal connections. Island 2: Connected lands at (1,4), (2,3), (2,4). Total: 2 islands.