Vùng kín


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Một bức ảnh được cho bởi một ma trận gồm các giá trị 0 và 1, một vùng trong bức ảnh là một vùng liên thông 4 láng giềng trên, dưới, phải, trái gồm toàn giá trị 0

Một vùng được gọi là vùng kín nếu như không có bất kỳ giá trị 0 nào nằm trên 1 trong 4 biên của bức ảnh.

Cho 1 bức ảnh, nhiệm vụ của bạn phải xác định số các vùng kín

Trong ví dụ hình dưới đây có 5 vùng tuy nhiên chỉ có 3 vùng kín

Vung kin

Input

Dòng đầu gồm 2 số nguyên dương n, m tương ứng số hàng và số cột của ma trận ảnh \(1 \le n,m \le 200\)

Tiếp theo n dồng mỗi dòng gồm m giá trị 0 hoặc 1 thể hiện ma trận ảnh

Output

Một số nguyên là số vùng kín trong ảnh

Ví dụ

Input

7 8
0   1   0   0   1   1   0   1
1   1   1   1   1   1   0   1
1   0   0   0   1   1   0   1
1   1   1   0   1   1   1   1
1   0   1   1   1   0   1   0
1   0   1   0   1   0   0   0
1   0   1   1   1   1   1   1

Output

2
tichpx

Comments

There are no comments at the moment.