Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 1482
Partitions

Time Limit: 10 Seconds      Memory Limit: 1024 KB

Given a maze, you are to tell the number of partitions in it.


Input

The first line is an integer N (2 <= N <= 3000), the size of the maze.

The next N lines each has N 0-and-1's, 1 for an obstacle and 0 for an unoccupied space.

Two unoccupied spaces are in the same partition if:

1. They are adjacent (above, below, left/right to,but not diagonally), or

2. They are both connected with another unoccupied space.


Output

One number on a line - the number of partitions.

Sample Input

2
0 1
1 0


Sample Output

2



Author: PAN, Minghao
Source: ZOJ Monthly, January 2003
Submit    Status