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
const fi = '';
fo = '';
maxN = 1000;
dx:array[1..8] of integer=(-1,-1,-1,0,0,1,1,1);
dy:array[1..8] of integer=(-1,0,1,-1,1,-1,0,1);
var qx, qy : array[1..10000] of longint;
a : array[0..maxN,0..maxN] of char;
count, i, j, m, n : longint;
procedure init;
var i, j : longint;
begin
readln(n,m);
fillchar(a,sizeof(a),'.');
for i:=1 to n do
begin
for j:=1 to m do read(a[i,j]);
readln;
end;
end;
procedure bfs(u,v:longint);
var x,y,xx,yy,first,last,k:longint;
begin
first:=1;
last:=1;
qx[first]:=u;
qy[first]:=v;
repeat
x:=qx[first];
y:=qy[first];
inc(first);
for k:=1 to 8 do
begin
xx:=x+dx[k];
yy:=y+dy[k];
if a[xx,yy]='W' then
begin
a[xx,yy]:='.';
inc(last);
qx[last]:=xx;
qy[last]:=yy;
end;
end;
until first > last;
end;
begin
assign(input,fi);reset(input);
assign(output,fo);rewrite(output);
init;
count:=0;
for i:=1 to n do
for j:=1 to m do
if a[i,j]='W' then
begin
inc(count);
a[i,j]:='.';
bfs(i,j);
end;
writeln(count);
close(input);close(output);
end.
