Bessie nhai chồi cỏ mềm và suy nghĩ về vũ trụ như bò thường làm. Cô chỉ thích cỏ trên đồng rộng ở độ cao nền của trang trại. Chỉ cao hơn 1 mét, cỏ đã cứng và kém ngon; càng cao càng dở.

Tiếp tục nhai, cô nhận ra cỏ dở mọc trên sườn đồi, tạo thành các “đảo” giữa biển cỏ mềm, xanh, ngon và dồi dào.

Bessie mặc áo phòng thí nghiệm và quyết định đếm đảo. Cô tạo bản đồ chia đồng thành $R$ hàng ($1 \lt R \le 1,000$) và $C$ cột ($1 \lt C \le 1,000$) ô vuông $1 \times 1$ mét. Cô đo độ cao trên nền ở mỗi ô và làm tròn thành số nguyên không âm. Cô đói bụng nhận thấy cỏ ngon đều có độ cao 0.

Cô bắt đầu đếm. Hai ô kề theo chiều ngang, dọc hoặc chéo thuộc cùng một đảo.

Cô đếm được bao nhiêu đảo cỏ dở trên mỗi bản đồ cho trước?

Dữ liệu vào

• Dòng $1$: hai số nguyên cách nhau bởi dấu cách: $R$, $C$.

• Các dòng $2,\ldots,R+1$: dòng $i+1$ mô tả hàng $i$ bằng $C$ số nguyên cách nhau bởi dấu cách.

Dữ liệu ra

• Dòng $1$: một số nguyên là số đảo.

Ví dụ

Dữ liệu vào 1

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

Dữ liệu ra 1

2

Ghi chú

Có hai đảo: đảo lớn bên trái kéo xuống tận đáy qua một kết nối chéo, còn đảo nhỏ ở góc trên phải.

Tác giả bài toán: Fatih, 2008