(10,0 ĐIỂM) - SỐ HÌNH CHỮ NHẬT TRÊN LƯỚI. TRÊN MỘT TỜ GIẤY KẺ...

Bài 1(10,0 điểm) - Số hình chữ nhật trên lưới.

Trên một tờ giấy kẻ ơ vuơng, kích thước N x N người ta tạo ra một số hình chữ nhật bằng cách định vị một số ơ liên tiếp

kề nhau, các hình chữ nhật này từng đơi một khơng giao nhau, khơng liền kề theo phép kề đỉnh. Cho bảng A (N x N), giá trị

phần tử của bảng được xác định như sau:

A[i,j] = 1 nếu ơ tương ứng trên tờ giấy thuộc một hình chữ nhật nào đấy.

A[i,j] = 0 nếu ơ tương ứng trên tờ giấy khơng thuộc một hình chữ nhật nào cả.

Hãy tìm số lượng các hình chữ nhật và các tọa độ đỉnh trái trên, phải dưới của mỗi hình chữ nhật trong bảng.

Dữ liệu vào lấy từ file văn bản “HCN.INP” dịng đầu ghi số N. N dịng tiếp theo mỗi dịng là xâu nhị phân độ dài N, giá

trị 1 nếu ơ tương ứng thuộc một hình chữ nhật, giá trị 0 nếu ơ tương ứng khơng thuộc một hình chữ nhật nào cả.

Kết quả ghi ra file văn bản “HCN.OUT” theo cấu trúc:

- Dịng đầu ghi số M là số hình chữ nhật cĩ trong bảng.

- M dịng tiếp theo mỗi dịng ghi 4 số p, q, r, s với ý nghĩa: cặp số p, q là tọa độ đỉnh trái trên, cặp số r, s là tọa độ đỉnh

phải dưới của một hình chữ nhật trong M hình chữ nhật cĩ trên bảng.

Ví dụ:

HCN.INP

HCN.OUT

7

1110011

5

0111000

1 1 2 3

0111011

1 6 2 7

0000011

3 2 4 4

1111011

4 6 6 7

1111000

6 1 7 4