Đảo Chiều Trọng Lực

Đ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ột lưới ô vuông $N \times M$ gồm các ký tự: . (ô trống), # (tường), C (vị trí xuất phát), D (vị trí đích).

Trong lưới có tác dụng của trọng lực: ban đầu trọng lực hướng xuống dưới. Nhân vật sẽ rơi theo chiều trọng lực hiện tại cho đến khi chạm vào tường hoặc biên lưới. Nếu nhân vật rơi ra ngoài biên lưới, nhiệm vụ thất bại.

Khi đang đứng trên một bề mặt (tường hoặc biên), nhân vật có thể:

Di chuyển sang trái hoặc phải (sang ô trống kề cạnh), sau đó sẽ rơi lại theo trọng lực hiện tại.
Đảo chiều trọng lực: trọng lực đổi chiều (từ xuống thành lên, hoặc ngược lại), sau đó nhân vật rơi theo chiều mới.

Tìm số lần đảo chiều trọng lực tối thiểu để đưa nhân vật từ C đến D.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $M$ .
$N$ dòng tiếp theo: Mỗi dòng gồm $M$ ký tự mô tả lưới.

Dữ liệu ra

Một số nguyên duy nhất: số lần đảo chiều trọng lực tối thiểu, hoặc $- 1$ nếu không thể đến được đích.

Ràng buộc

$1 \leq N, M \leq 500$

Ví dụ

Input	Output	Giải thích
5 5 ##### #...# #...D #C... ##.##	3	Nhân vật đảo trọng lực lên, rơi lên trên, di chuyển sang phải, đảo lại, rơi xuống, di chuyển sang phải, đảo một lần nữa để đến D.
3 11 #..C###.#.. #.D.#.#.#.. ###.###.###	-1	Không thể đến được D.

Bình luận

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