9.29.2017

Hình chữ nhật

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