BCLKCOUN spoj PTIT – Đếm số ao

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCLKCOUN/

1. Đề bài BCLKCOUN spoj

Sau khi kết thúc OLP Tin Học SV, một số OLP-er quyết định đầu tư thuê đất để trồng rau.

Mảnh đất thuê là một hình chữ nhật N x M (1<=N<=100; 1<=M<=100) ô đất hình vuông. Nhưng chỉ sau đó vài ngày, trận lụt khủng khiếp đã diễn ra làm một số ô đất bị ngập :(( Mảnh đất biến thành một số các ao.

Các OLP-er quyết định chuyển sang nuôi cá 😀 Vấn đề lại nảy sinh, các OLP-er muốn biết mảnh đất chia thành bao nhiêu cái ao để có thể tính toánnuôi trồng hợp lý. Bạn hãy giúp các bạn ý nhé.

Chú ý: Ao là gồm một số ô đất bị ngập có chung đỉnh. Dễ nhận thấy là một ô đất có thể có tối đa 8 ô chung đỉnh.

INPUT:

* Dòng1: 2 số nguyên cách nhau bởi dấu cách: N và M

* Dòng 2..N+1: M kí tự liên tiếp nhau mỗi dòng đại diện cho 1 hàng các ô đất.

Mỗi kí tự là ‘W’ hoặc ‘.’ tương ứng với ô đất đã bị ngập và ô đất vẫn còn nguyên.

OUTPUT:

* Dòng 1: 1 dòng chứa 1 số nguyên duy nhất là số ao tạo thành.

SAMPLE INPUT :

10 12

W……..WW.

.WWW…..WWW

….WW…WW.

………WW.

………W..

..W……W..

.W.W…..WW.

W.W.W…..W.

.W.W……W.

..W…….W.

SAMPLE OUTPUT :

3

2. Gợi ý BCLKCOUN spoj PTIT

– Sử dụng BFS hoặc DFS để đếm số thành phần liên thông

3. Code tham khảo BCLKCOUN spoj PTIT

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *