Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Bản đồ một trang trại là một hình chữ nhật kích thước m×n được chia làm lưới ô vuông đơn vị, các hàng của lưới được đánh số từ 1 tới ~m~ từ trên xuống dưới và các cột của lưới được đánh số từ ~1~ tới ~n~ từ trái qua phải. Ô nằm trên giao của hàng ~x~, cột ~y~ được gọi là ô ~(x,y)~ và ô đó có độ cao là ~h_{xy}~.

Trong những ngày mưa tầm tã, mực nước dâng lên và trang trại bị ngập dần trong nước. Nếu mực nước là ~k~ thì những ô có độ cao ~≤ k~ được coi là ngập nước còn những ô có độ cao ~> k~ được coi là chưa ngập nước. Những ô chưa ngập nước tạo thành những "đảo" định nghĩa như sau: Hai ô chưa ngập nước được gọi là cùng đảo nếu ta có thể đi từ ô này tới ô kia bằng cách di chuyển qua các ô kề cạnh chưa ngập nước, ngược lại hai ô đó được coi là nằm trên hai đảo khác nhau. Ví dụ với bản đồ dưới đây, ta có 4 đảo khi mực nước bằng 2, có 2 đảo khi mực nước bằng 7

Yêu cầu: Giả sử trong những ngày mưa, mực nước dâng dần lên cho tới khi toàn bộ các ô đều ngập nước, xác định số đảo tại một thời điểm trong những ngày mưa mà tại thời điểm đó có nhiều đảo nhất.

Dữ liệu:

  • Dòng 1 chứa hai số nguyên dương ~m,n~ ≤ ~1000~
  • ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên dương, số thứ ~j~ là ~h_{ij}~≤ ~10^6~.

Các số trên một dòng của input file được ghi cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra một số nguyên duy nhất là số đảo tại thời điểm có nhiều đảo nhất.

Ví dụ
INPUT
6 6
9 1 8 1 5 4
7 1 8 1 5 5
7 7 8 1 1 1
1 1 1 1 6 6
3 3 1 6 6 1
3 3 1 6 1 1
OUTPUT
4

Comments

Please read the guidelines before commenting.


There are no comments at the moment.