Trên giấy kẻ ô khổ N x N có vẽ một số hình chữ nhật. Mỗi hình chữ nhật được tạo ra từ các ô nguyên vẹn, các hình chữ nhật khác nhau không chồng lên nhau và không tiếp xúc nhau.
Cho mảng A có kích thước N x N, trong đó A[i,j]=1 nếu ô [i,j] thuộc một hình chữ nhật nào đó, còn A[i,j] =0 trong trường hợp ngược lại. Hãy viết chương trình xác định số các hình chữ nhật có trong bảng.
Dữ liệu vào: Từ File văn bản RECT.INP có cấu trúc như sau:
- Dòng đầu tiên ghi số nguyên dương N (N<=250).
- N dòng tiếp theo mỗi dòng ghi N số 0 hoặc 1 là các phần tử của mảng, mỗi số viết cách nhau ít nhất một dấu cáchkhoảng.trắng .
Dữ liệu ra: Ghi ra File văn bản RECT.OUT gồm duy nhất một số là số hình chữ nhật tìm được.
Giải
const
fi='rect.inp';
fo='rect.out';
Var
i,j,b,c,d,x,y,n:Integer;
f: text;
a: array[1..250,1..250] of byte;
BEGIN
assign(f,fi);
reset(f);
readln(f,n);
for i:=1 to n do
begin
for j:=1 to n do read(f,a[i,j]);
readln(f);
end;
close(f);
for i:=1 to n do
for j:=1 to n do
if a[i,j]=1 then
begin
d:=d+1;
b:=i; c:=j;
repeat
c:=c+1;
until (a[i,c]=0) or (c=n);
repeat
b:=b+1;
until (a[b,j] =0) or (b=n);
for x:=i to b do
for y:=j to c do
a[x,y]:=0;
end;
assign(f,fo);
rewrite(f);
writeln(f,d);
close(f);
END.
No comments:
Post a Comment
Cảm ơn bạn đã nhận xét