Giấc mơ của Bessie

Đ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 mê cung $N \times M$ ô, mỗi ô có một màu:

Đỏ (0): Không thể đi qua.
Hồng (1): Đi qua bình thường.
Cam (2): Đi qua và được "mùi cam".
Xanh (3): Chỉ đi qua được nếu đang có mùi cam.
Tím (4): Trượt tiếp theo hướng đang đi cho đến khi gặp ô không tím hoặc chướng ngại vật. Mất mùi cam khi trượt trên ô tím.

Bắt đầu từ ô $(1, 1)$ (góc trên trái), tìm số bước ít nhất để đến ô $(N, M)$ (góc dưới phải). Mỗi bước di chuyển sang ô kề (trên, dưới, trái, phải). Nếu không thể đến được, in $- 1$ .

Dữ liệu vào

Dòng đầu: hai số nguyên $N$ và $M$ .
$N$ dòng tiếp theo: mỗi dòng $M$ số nguyên ( $0$ - $4$ ) — màu các ô.

Dữ liệu ra

Một số nguyên duy nhất — số bước ít nhất, hoặc $- 1$ .

Ràng buộc

$1 \leq N, M \leq 1000$
Ô $(1, 1)$ và $(N, M)$ luôn là hồng (1).

Ví dụ

Input	Output	Giải thích
4 4 1 0 2 1 1 1 4 1 1 0 4 0 1 3 1 1	10	Đi xuống, sang phải qua ô cam, trượt trên ô tím, quay lại lấy mùi cam rồi đi qua ô xanh.

Bình luận

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