Link Sub: http://www.spoj.com/PTIT/problems/BCLKCOUN/
Người Gửi: Dương Lee
- Problem:
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 :((
Due to recent rains, water has pooled in various places in Farmer
John's field, which is represented by a rectangle of N x M (1 <= N
<= 100; 1 <= M <= 100) squares. Each square contains either water
('W') or dry land ('.'). Farmer John would like to figure out how
many ponds have formed in his field. A pond is a connected set of
squares with water in them, where a square is considered adjacent
to all eight of its neighbors.
Given a diagram of Farmer John's field, determine how many ponds he has.
PROBLEM NAME: lkcount
INPUT FORMAT:
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: M characters per line representing one row of Farmer
John's field. Each character is either 'W' or '.'. The
characters do not have spaces between them.
SAMPLE INPUT (file lkcount.in):
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
OUTPUT FORMAT:
* Line 1: The number of ponds in Farmer John's field.
SAMPLE OUTPUT (file lkcount.out):
3
OUTPUT DETAILS:
There are three ponds: one in the upper left, one in the lower left,
and one along the right side.
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á :D 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án
nuô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.
Example:
* Dòng 1: 1 dòng chứa 1 số nguyên duy nhất là số ao tạo thành.
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.
Output:
3
- Solution:
Bài này mình sử dụng phương pháp DFS đệ quy tìm số thành phần liên thông. Sơ lược qua về khởi tạo ban đầu:
- Tạo dinh[R][C]: với lần lượt các đỉnh từ 1->R*C;
- Duyệt theo 8 hướng (lên, lên trái, trái, xuống trái, xuống, xuống phải, phải, lên phải) và đánh dấu;
Các bạn cũng có thể sử dụng BFS.
2 nhận xét
nhận xétcảm ơn cậu bài hướng dẫn rất hay
Replycòn một chút vấn đề tớ chưa hiểu nhờ cậu giải đáp giúp tớ với nhé
tớ chưa hiểu cách cậu xây dựng mảng xqX, và xqY, ở đây tớ chưa hình dung ra hướng đi, cậu giải thích rõ hơn giúp tớ đoạn này được không?
chào cậu, lại là tớ đây ^^ (tớ là người đặt câu hỏi về xqX[], xqY[])
Replyxin lỗi cậu hồi nãy tớ chưa suy nghĩ kỹ, sau một hồi vò đầu thì tớ hiểu rồi, cảm ơn cậu nhiều nhé ^^