HVT_QV - Robot quét vôi

Một quần thể nhà cao tầng được xây dựng trên một nền hình chữ nhật, trên đó được chia thành M×N ô vuông đơn vị (M dòng, N cột). Các dòng được đánh số từ 1 đến M, các cột được đánh số từ 1 đến N. Người ta xem khu nhà được tạo bởi các khối có đáy là một ô vuông với những chiều cao nào đó mà người ta gọi là những đơn nguyên. Một đơn nguyên được xác định bởi tọa độ dòng, cột của ô đáy và chiều cao tương ứng. Một khối nhà được định nghĩa là một tập hợp các đơn nguyên có đáy tạo thành một miền gồm các ô kề cạnh. Ví dụ hình vẽ dưới đây mô tả một quần thể gồm 3 khối nhà: Người ta đánh số các khối nhà bằng những số nguyên liên tục bắt đầu từ 1 theo trình tự duyệt các ô đáy theo từng dòng từ 1 đến M và trên mỗi dòng, duyệt các ô đáy theo từng cột từ 1 đến N. Ví dụ, các khối nhà cho trong hình vẽ bên dưới được đánh số theo thứ tự các ô đáy (có màu xám, con số là chiều cao). Người ta muốn quét vôi các bức tường xung quanh tất cả các khối nhà (không quét vôi phía trên nóc nhà)

1

2

3

0

2

1

1

0

1

0

0

1

2

1

1

0

0

1

0

0

0

1

1

0

 

 

 

 

Yêu cầu: Hãy xác định số lượng các khối nhà, tổng số diện tích quét vôi, khối nhà có diện tích quét vôi lớn nhất và diện tích này.

Input

- Dòng đầu tiên ghi 2 số nguyên M, N (0 < M, N ≤100)

- M dòng tiếp theo, mỗi dòng ghi N số nguyên thể hiện chiều cao của đơn nguyên (0 ≤ H[i, j] ≤ 10.000 với i = 1, 2, …, M; j = 1, 2, …, N), với quy ước bằng 0 khi đơn nguyên này không có. Giả thiết rằng các giá trị này đều là các số nguyên và tính theo đơn vị một cạnh của ô vuông. Các số trên cùng môt dòng ghi cách nhau ít nhất một dấu cách.

Output

- Dòng đầu tiên ghi số lượng các khối nhà;

- Dòng thứ hai ghi tổng diện tích cần quét vôi;

- Dòng thứ ba ghi số hiệu của khối nhà có diện tích quét vôi lớn nhất và giá trị diện tích của khối nhà này. Nếu có nhiều khối nhà có cùng diện tích quét vôi lớn nhất thì đưa ra khối nhà có số hiệu nhỏ nhất.

Example

Input:

4 6

1 2 3 0 2 1

1 0 1 0 0 1

2 1 1 0 0 1

0 0 0 1 1 0 Output:

3

50

1 30

Added by:Vương Trung Hiếu Nghĩa
Date:2014-04-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Sưu tầm

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.