Một khu vườn có dạng hình chữ nhật
có chiều dài là D và chiều rộng là R (mét). Giả sử khu vườn được chia ra làm
D*R ô vuông cạnh độ dài 1 mét. Trong một số ô vuông có trồng cây. Một xe cắt cỏ
có dạng một hình vuông kích thước 3*3 (mét) đặt tại một vị trí nào đó trong khu
vườn. Xe cắt cỏ có thể di chuyển sang trái, sang phải, lên trên, xuống dưới 1
mét. Xe không thể di chuyển lên các ô có cây. Xe cắt cỏ sẽ dọn dẹp được những
ô mà nó đi qua. Hãy xác định các ô mà xe cắt cỏ có thể dọn dẹp được.
Dữ
liệu vào file Catco.inp dòng đầu khi
hai số nguyên dương D, R (5<=D, R<=100). Dòng thứ i trong số D dòng tiếp
theo ghi R ký hiệu mô tả trạng thái của lưới ô vuông: ‘+’ cho biết vị trí cây, ‘.’
Cho biết ô vuông rỗng. ‘M’ cho biết tâ, của vị trí xe cắt cỏ. Các ký hiệu được
ghi cách nhau một dấu cách.
Kết
quả ra file Catco.out: Ghi ra số ô
có được cắt.
CODE THAM KHẢO:
var f:text;
a,b:array[0..101,0..101] of char;
x,y,i,j,n,m:byte;
ans:integer;
c:char;
procedure Enter;
begin
assign(f,'catco.inp');
reset(f);
readln(f,n,m);
for i:=1 to n do
begin
for j:=1 to m do
begin
if j<m then read(f,a[i,j],c) //c để đọc khoảng trắng
else read(f,a[i,j]);
if a[i,j]='M' then //Đánh dấu ô M
begin
x:=i;
y:=j;
end;
end;
readln(f);
end;
close(f);
end;
procedure Init;
begin
for i:=1 to m do //Tạo viền giới hạn Trên - Dưới
begin
a[0,i]:='+';
a[n+1,i]:='+';
end;
for i:=1 to n do //Tạo viền giới hạn Trái - Phải
begin
a[i,0]:='+';
a[i,m+1]:='+';
end;
b:=a;
for i:=x-1 to x+1 do
for j:=y-1 to y+1 do a[i,j]:='O'; //Khởi tạo ô cỏ 3x3 vị trí ban đầu
end;
procedure Mark1(u,v:byte);
begin
a[u,v]:='O';
a[u,v-1]:='O';
a[u,v+1]:='O';
end;
procedure Mark2(u,v:byte);
begin
a[u,v]:='O';
a[u-1,v]:='O';
a[u+1,v]:='O';
end;
procedure Solve(u,v:byte);
begin
//Đi lên
if (u+2<=n+1) then
if (a[u+2,v]<>'+') and (a[u+2,v-1]<>'+') and (a[u+2,v+1]<>'+') and (((a[u+2,v]='.') or (a[u+2,v-1]='.') or (a[u+2,v+1]='.'))) then
begin
Mark1(u+2,v); //Đánh dấu
Solve(u+1,v);
end;
//Đi xuống
if (u-2>=0) then
if (a[u-2,v]<>'+') and (a[u-2,v-1]<>'+') and (a[u-2,v+1]<>'+') and ((a[u-2,v]='.') or (a[u-2,v-1]='.') or (a[u-2,v+1]='.')) then
begin
Mark1(u-2,v); //Đánh dấu
Solve(u-1,v);
end;
//Qua phải
if (v+2<=m+1)then
if (a[u,v+2]<>'+') and (a[u-1,v+2]<>'+') and (a[u+1,v+2]<>'+') and ((a[u,v+2]='.') or (a[u-1,v+2]='.') or (a[u+1,v+2]='.')) then
begin
Mark2(u,v+2); //Đánh dấu
Solve(u,v+1);
end;
//Qua trái
if (v-2>=0) then
if (a[u,v-2]<>'+') and (a[u-1,v-2]<>'+') and (a[u+1,v-2]<>'+') and ((a[u,v-2]='.') or (a[u-1,v-2]='.') or (a[u+1,v-2]='.')) then
begin
Mark2(u,v-2); //Đánh dấu
Solve(u,v-1);
end;
end;
procedure Result;
begin
for i:=1 to n do
for j:=1 to m do
if a[i,j]<>b[i,j] then inc(ans); //Đếm những ô đã cắt cỏ
write(f,ans-1); //Không tính ô M
end;
begin
Enter;
assign(f,'catco.out'); rewrite(f);
Init;
Solve(x,y);
Result;
close(f)
end.
Đăng nhận xét