Máy kéo

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho bản đồ $N \times N$ ô vuông, mỗi ô $(i, j)$ có độ cao $h_{i, j}$ . Một chiếc máy kéo có thể di chuyển giữa hai ô kề nhau (ngang hoặc dọc) nếu chênh lệch độ cao giữa chúng không vượt quá $K$ .

Tìm giá trị $K$ nhỏ nhất sao cho từ một ô nào đó, máy kéo có thể đến được ít nhất $⌈ N^{2} / 2 ⌉$ ô khác nhau.

Dữ liệu vào

Dòng $1$ : Số nguyên $N$ .
$N$ dòng tiếp: Mỗi dòng chứa $N$ số nguyên biểu diễn độ cao các ô trong hàng đó.

Dữ liệu ra

Một số nguyên — giá trị $K$ nhỏ nhất thỏa mãn yêu cầu.

Ràng buộc

$1 \leq N \leq 500$
$0 \leq h_{i, j} \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
5 0 0 0 3 3 0 0 0 0 3 0 9 9 3 3 9 9 9 3 3 9 9 9 9 3	3	Với $K = 3$ : 8 ô có độ cao 0 và 8 ô có độ cao 3 kết nối thành vùng 16 ô $\geq ⌈ 25 / 2 ⌉ = 13$ .

Bình luận

Không có bình luận tại thời điểm này.