#575. HOUSE - Robot xây nhà

Có một số con Rô-bốt xây nhà trên một mảnh đất hình vuông, mảnh đất đó được chia thành lưới ô vuông đơn vị kích thước . Vì Rô-bốt được lập trình xây nhà khá máy móc, nên hai ngôi nhà do cùng một con Rô-bốt xây nên sẽ có kích thước và hình dạng đáy giống hệt nhau (Có thể đặt chồng khít lên nhau qua một phép dời hình), hai ngôi nhà do hai con Rô-bốt khác nhau xây nên thì có ít nhất một ô khác nhau.

Khi công trình hoàn thành, các ngôi nhà được xây hoàn toàn tách biệt (không có hai ngôi nhà nào chung ô, chung tường, nhưng có thể chung góc tường). Bản đồ của khu đất đã được chụp ảnh và mã hoá dưới dạng một ma trận vuông kích thước , trong đó cho biết ô của mảnh đất thuộc một ngôi nhà nào đó còn cho biết ô của mảnh đất vẫn còn để trống.

Vấn đề đặt ra là khi có bản đồ khu nhà trong tay, hãy xác định số con rô bốt tham gia xây nhà và chỉ rõ con rô bốt nào xây ngôi nhà nào.

Dữ liệu vào:

• Dòng đầu ghi số nguyên dương .
• dòng tiếp theo, dòng thứ ghi số, số thứ là .

Dữ liệu ra:

• Ghi số con rô-bốt tham gia xây nhà.

Ví dụ:

Dữ liệu vào:

9
1 1 1 0 1 0 0 0 1
1 0 0 0 1 1 0 1 1
1 1 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0
1 0 0 1 0 0 0 0 0
0 0 1 1 0 1 0 0 0
1 0 0 0 0 1 0 0 1
1 0 1 0 0 1 1 0 1
1 1 1 1 1 0 0 1 1

Dữ liệu ra:

4