Trượt Tuyết Việt Dã

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.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 một lưới $M \times N$ ô vuông, mỗi ô có một giá trị độ cao nguyên. Một số ô được đánh dấu là điểm kiểm tra (waypoint).

Hai ô kề nhau (theo 4 hướng: bắc, nam, đông, tây) được coi là có thể di chuyển giữa nhau nếu chênh lệch độ cao tuyệt đối của chúng $\leq D$ .

Tìm giá trị $D$ nhỏ nhất sao cho tất cả các điểm kiểm tra đều liên thông với nhau (có thể đến được từ bất kỳ điểm kiểm tra nào đến bất kỳ điểm kiểm tra nào khác thông qua các ô trung gian).

Dữ liệu vào

Dòng 1: Hai số nguyên $M$ và $N$ ( $1 \leq M, N \leq 500$ ).
$M$ dòng tiếp theo: Mỗi dòng gồm $N$ số nguyên là độ cao của từng ô ( $0 \leq h \leq 10^{9}$ ).
$M$ dòng tiếp theo: Mỗi dòng gồm $N$ số nguyên $0$ hoặc $1$ , trong đó $1$ chỉ điểm kiểm tra.

Dữ liệu ra

Một số nguyên duy nhất: giá trị $D$ nhỏ nhất.

Ràng buộc

$1 \leq M, N \leq 500$
$0 \leq h \leq 10^{9}$
Luôn có ít nhất một điểm kiểm tra.

Ví dụ

Input	Output	Giải thích
3 5 20 21 18 99 5 19 22 20 16 26 18 17 40 60 80 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1	21	Với $D = 21$ , ba điểm kiểm tra (góc trên-trái, góc trên-phải, góc dưới-phải) đều liên thông. Với $D = 20$ , điểm góc trên-phải bị cô lập.

Bình luận

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