Một vùng đất rừng hình chữ nhật được chia thành một lưới các ô vuông gồm M hàng và N cột mà ở mỗi ô có thể trồng được một cây (1<=M,N<=15). Các hàng được đánh số từ 1 đến M theo thứ tự từ trên xuống dưới; các cột được đánh số từ 1 đến N theo thứ tự từ trái qua phải; ô năm trên hàng i cột j được kí hiệu là ô (i,j). Trước đây toàn bộ những ô này đã được trồng cây nhưng do chăm sóc kém nên một số cây đã chết. Người ta muốn sử dụng một robot trồng cây để trồng lại các cây bị chết. Robot này sau khi trồng cây xong ở một ô có khả năng di chuyển đến một trong các ô liền kề để trồng tiếp. Robot không được di chuyển ra khỏi ngoài vùng đất và không được tiến vào ô đã có cây dù là cây có trước hay là cây do chính robot vừa trồng. Ban đầu robot được đưa vào vị trí có cây chết ở hàng X, cột Y và đó là ô đầu tiên robot phải trồng cây.
Yêu cầu: Hãy tính số lượng cây lớn nhất mà robot có thể trồng được.
Dữ liệu vào: Đọc từ file văn bản BL3.INP có cấu trúc như sau:
- Dòng đầu tiên ghi 4 số tự nhiên M, N, X, Y (1<=M, N, X, Y <= 15).
M dòng tiến theo mỗi dòng có N số 0 hoặc 1, hai số liên tiếp cách nhau bởi một khoảng trống. Số thứ j trong dòng thứ i của M dòng này nếu bằng 0 thì thể hiện cây ở ô (i,j) đã chết; nếu
bằng 1 thì thể hiện ô (i,j) đã có cây, Robot không được đi qua cũng như trồng lại.
Dữ liệu ra: Ghi ra tệp văn bản BL3.OUT số nguyên S là số cây lớn nhất mà robot có thể trồng được.
Ví dụ:
BL3.INP BL3.OUT
6 6 6 4 14
1 1 0 1 1 1
1 1 0 0 0 0
0 0 0 1 1 0
0 0 0 0 0 1
1 1 0 0 1 1
1 1 1 0 1 1
Loi giai tham khao
var f1,f2:text;
ReplyDeletea,b:array[1..100,1..100] of boolean;
m,n,x,y,i,j,k:byte;
comax,max:word;
Procedure taoteptin;
begin
assign(f1,'TrongCay.inp');
assign(f2,'TrongCay.out');
{$I-} RESET(F1);{$I+}
IF IORESULT<>0 THEN
BEGIN
rewrite(f1);
reset(f1);
END;
REWRITE(F2);
end;
Procedure nhap;
var i,j,k:byte;
begin
readln(F1,m,n,x,y);
for i:=1 to m do
begin
for j:=1 to n do
begin
read(F1,k);
if k=1 then a[i,j]:=false else a[i,j]:=true;
end;
readln(f1);
end;
end;
procedure vet(i,j:byte);
begin
inc(comax);
b[i,j]:=true;
if comax>max then max:=comax;
if (i1) and (a[i-1,j]=true) and (b[i-1,j]=false) then vet(i-1,j);
if (j1) and (a[i,j-1]=true) and (b[i,j-1]=false) then vet(i,j-1);
dec(comax);
b[i,j]:=false;
end;
begin
taoteptin;
nhap;
fillchar(b,sizeof(b),false);
comax:=0; max:=0;
vet(x,y);
writeln(f2,max);
CLOSE(F1); CLOSE(F2);
end.