No.697 How Many Ponds Are There?
yuki2006Problem Statement
You are given an $H \times W$ field. The field contains only $0$ and $1$.
$0$ is a ground cell and $1$ is a water cell.
A single pond is what is formed by joining $1$s that are connected vertically or horizontally.
Diagonal cells are not connected.
Even a single cell counts as a pond.
How many ponds are there in this field?
Everything outside the field is considered ground.
(The time limit is generous, but be careful about the number of function calls and the memory limit.)
This may be tough for LL languages. It may be adjusted at a later date.
Input
$H\ W$
$A_{1,1} \dots A_{W,1}$
$\dots$
$A_{1,H} \dots A_{W,H}$
$1\le H,W \le 3000$
$A_{i,j}$ is $0$ or $1$
Output
Output the number of ponds.
Sample
Sample 1
Input
4 3 1 0 1 0 1 0 1 0 1 0 1 0
Output
6
There are 6 pieces of water consisting of 1 cell each.
Even a single cell is a pond, so there are 6 ponds.
Sample 2
Input
4 3 1 1 1 0 1 0 1 0 1 1 1 1
Output
2
The water cells join together to form 2 ponds.
Sample 3
Input
3 4 0 0 0 0 0 0 0 0 0 0 0 0
Output
0
There may be no water at all.
Sample 4
Input
3 4 1 1 1 1 1 1 1 1 1 1 1 1
Output
1
Everything is water and forms one pond.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。