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 (Ví dụ : Hình vẽ dưới đây có 4 hình chữ nhật).1000000001110010111001011100000000000001110000111h1 : [3,2] tới [4,4].h2 : [5,2] tới [5,4].h3 : [1,3] tới [1,4].h4 : [5,6] tới [7,7].(có thể tìm các hình khác nhưng trong vd trên chỉ có 4 hình)Cho mảng A có...
Đọc tiếp
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 (Ví dụ : Hình vẽ dưới đây có 4 hình chữ nhật).
1 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 1 | 0 | 0 |
1 | 0 | 1 | 1 | 1 | 0 | 0 |
1 | 0 | 1 | 1 | 1 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 1 | 1 | 1 |
0 | 0 | 0 | 0 | 1 | 1 | 1 |
h1 : [3,2] tới [4,4].
h2 : [5,2] tới [5,4].
h3 : [1,3] tới [1,4].
h4 : [5,6] tới [7,7].
(có thể tìm các hình khác nhưng trong vd trên chỉ có 4 hình)
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 vs03.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ách.
Dữ liệu ra: Ghi ra File văn bản vs03.OUT gồm duy nhất một số là số hình chữ nhật tìm được.
Ví dụ:
Test | CountRec.inp | CountRec.out |
1 | 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 0 |
2 | 7 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 | 4 |
Giả sử dùng các hình chữ nhật 1x4 để phủ các ô vuông của bảng 14x14 mà không bị chồng chất lên nhau và không có phần nào bị thừa
thì cần số hình chữ nhật 1x4 là : 14x14 : 1x4 = 49 ( hình )
Ta dùng 36 hình chữ nhật 1x4 để sắp xếp thành bảng lớn khác 12x12, hình vẽ :
Như vậy để có bảng 14x14 ta phải lắp thêm 13 hình chữ nhật 1x4 nữa
Ta thấy không thể lắp vừa => Không thể dùng các hình chữ nhật 1x4 để phủ các ô vuông của bảng 14x14 mà không bị chồng chất lên nhau và không có phần nào bị thừa.