Đánh Giá Độ Khó Đường Trượt

Điểm: 1,00 (OI)

Giới hạn thời gian: 3.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 lưới độ cao $M \times N$ ô vuông. Độ khó của một điểm xuất phát $S$ là giá trị $D$ nhỏ nhất sao cho từ $S$ , di chuyển qua các ô kề (lên, xuống, trái, phải) với điều kiện chênh lệch độ cao giữa hai ô kề không vượt quá $D$ , có thể đến được ít nhất $T$ ô (tính cả $S$ ).

Tính tổng độ khó của tất cả các điểm xuất phát.

Dữ liệu vào

Dòng 1: Ba số nguyên $M$ , $N$ , $T$ ( $1 \leq M, N \leq 500$ ; $1 \leq T \leq M \cdot N$ ).
$M$ dòng tiếp theo: mỗi dòng gồm $N$ số nguyên — độ cao các ô ( $0 \leq h \leq 10^{9}$ ).
$M$ dòng tiếp theo: mỗi dòng gồm $N$ số $0$ hoặc $1$ — $1$ đánh dấu điểm xuất phát.

Dữ liệu ra

Tổng độ khó của tất cả điểm xuất phát (có thể vượt $2^{32}$ ).

Ràng buộc

$1 \leq M, N \leq 500$
$0 \leq h_{i, j} \leq 10^{9}$
$1 \leq T \leq M \cdot N$

Ví dụ

Input	Output	Giải thích
3 5 10 20 21 18 99 5 19 22 20 16 17 18 17 40 60 80 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1	24	Điểm $(0, 0)$ : cần $D = 4$ để đến $10$ ô. Điểm $(2, 4)$ : cần $D = 20$ . Tổng $= 4 + 20 = 24$ .
2 3 4 10 12 15 11 13 20 1 0 0 0 0 1	7	Điểm $(0, 0)$ : cần $D = 2$ để đến $4$ ô. Điểm $(1, 2)$ : cần $D = 5$ . Tổng $= 2 + 5 = 7$ .

Bình luận

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