Vanya và Kho Báu

Điểm: 8,00 (OI)

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

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++

Vanya đang ở trong một cung điện được biểu diễn bằng lưới $n \times m$ . Mỗi ô chứa đúng một rương, rương ở hàng $i$ cột $j$ có loại $a_{i j}$ .

Mỗi rương có loại $x \leq p - 1$ chứa một chiếc chìa khóa mở được mọi rương loại $x + 1$ . Tất cả rương loại $1$ không bị khóa. Có đúng một rương loại $p$ và nó chứa kho báu.

Vanya xuất phát từ ô $(1, 1)$ (góc trên trái). Khoảng cách giữa hai ô $(r_{1}, c_{1})$ và $(r_{2}, c_{2})$ là $| r_{1} - r_{2} | + | c_{1} - c_{2} |$ (khoảng cách Manhattan). Tính tổng quãng đường nhỏ nhất Vanya phải đi để đến được rương loại $p$ .

Vanya phải mở rương theo thứ tự loại tăng dần: trước tiên đến một rương loại $1$ , rồi một rương loại $2$ , …, rồi rương loại $p$ . Tại mỗi bước, Vanya có thể di chuyển tự do trên lưới (không có chướng ngại); chỉ cần lượt thăm các rương đúng thứ tự loại.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $n$ , $m$ , $p$ .
$n$ dòng tiếp theo, mỗi dòng gồm $m$ số nguyên $a_{i j}$ — loại của rương tại ô $(i, j)$ .

Dữ liệu ra

In ra một số nguyên — tổng quãng đường nhỏ nhất.

Ràng buộc

$1 \leq n, m \leq 300$
$1 \leq p \leq n \cdot m$
$1 \leq a_{i j} \leq p$
Với mọi $x$ từ $1$ đến $p$ , tồn tại ít nhất một rương loại $x$ .
Có đúng một rương loại $p$ .

Ví dụ

Input	Output	Giải thích
3 4 3 2 1 1 1 1 1 1 1 2 1 1 3	5	Đi từ $(1, 1)$ đến ô $(1, 2)$ (loại 1, $1$ bước), rồi sang ô $(3, 1)$ (loại 2, $3$ bước), rồi đến ô $(3, 4)$ (loại 3, $3$ bước). Có đường tối ưu khác cho tổng quãng đường bằng $5$ .
3 3 9 1 3 5 8 9 7 4 6 2	22	$p = 9$ , phải đi qua đủ chín loại theo thứ tự $1 \to 2 \to \dots \to 9$ .
3 4 12 1 2 3 4 8 7 6 5 9 10 11 12	11	Các rương được xếp dạng "rắn" nên đi tuần tự dọc theo đó.

Bình luận

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