Lập trình robot(bản khó)(SUB-CHAPTER) - Giải mã mê cung

Điểm: 50,00 (OI)

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

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

Input: stdin

Output: stdout

Nguồn bài:

Cpascal

Dạng bài

Ngôn ngữ cho phép

C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Sau khi tiến vào mỗi người chia ra một đường để tìm tòi abcnickname chọn bên phải. Còn Cpascal thì chọn bên trái. Sau một lúc abcnickname đã tìm thấy cho mình một tấm bia kỳ lạ có khắc một cái hình rất giống mê cung trước đó mà abcnickname và Cpascal đã phải trải qua. Nhìn đi nhìn lại một hồi thấy có một ghi chú như sau "Lập trình robot, giải chúng, vượt qua các chứa ngại vật và tìm con đường tới đích nhanh nhất có thể" sau khi đọc qua luật chơi đó abcnickname chấp nhận thử thách. Anh ấy đã code 8 ngày 8 đêm. Sử dụng 8 chiếc máy tính và 800 năm học tin học để có thể giải được câu đố đó. Nhưng dù cố gắng đến đâu thì abcnickname chỉ có thể giải được 8 phần và phải nhờ bạn giải nốt 2 phần còn lại. Nếu được thì anh ấy sẽ rất cảm kích!

Yêu cầu: cho con robot tìm đường ngắn nhất có thể

Dữ liệu vào

Chỉ số của con robot như sau

Và vị trí của chúng ~x~ và ~y~ (đảm bảo vị trí của con robot không trùng khớp với vị trí của bức tường)

Sau đó là kích thước của bản đồ gồm ~n~ x ~n~ (~10 ≤ n ≤ 100~) mỗi ô bản đồ cần phải điền như sau

Nếu ô trống thì ghi ~0~
Nếu ô tường thì ghi ~8~ (bức tường khiến robot không thể đi qua)
Nếu là điểm kết thúc thì ghi ~9~ (điểm kết thúc có thể nằm ở bất cứ nơi nào!)
Bắt buộc phải có lời giải và điểm kết thúc

Dữ liệu ra

In ra chỉ số máu và số bước đi ngắn nhất!(Ưu tiên nước đi thay vì chỉ số máu)

Ví dụ

Input: 01

1 1
12 12
0 0 0 0 8 0 0 0 0 0 0 0 
8 8 8 0 8 0 8 8 8 8 8 0 
8 0 8 0 8 0 8 0 0 0 8 0 
8 0 8 0 8 8 8 0 8 0 8 0 
8 0 8 0 8 0 0 0 8 0 0 0 
8 0 8 0 8 0 8 8 8 8 8 0 
8 0 8 0 8 0 8 0 0 0 8 0 
8 0 8 0 8 0 8 0 8 8 8 0 
8 0 8 0 0 0 8 0 0 0 0 0 
8 0 8 8 8 8 8 0 8 8 8 8 
8 0 0 0 0 0 0 0 0 0 0 0 
8 8 8 8 8 8 8 8 8 8 8 9

Output: 01

Đường đi của chúng

0 * * * 8 0 0 0 0 0 0 0 
8 8 8 * 8 0 8 8 8 8 8 0 
8 0 8 * 8 0 8 * * * 8 0 
8 0 8 * 8 8 8 * 8 * 8 0 
8 0 8 * 8 * * * 8 * * * 
8 0 8 * 8 * 8 8 8 8 8 * 
8 0 8 * 8 * 8 0 0 0 8 * 
8 0 8 * 8 * 8 0 8 8 8 * 
8 0 8 * * * 8 * * * * * 
8 0 8 8 8 8 8 * 8 8 8 8 
8 0 0 0 0 0 0 * * * * * 
8 8 8 8 8 8 8 8 8 8 8 9

Bình luận

Hãy đọc nội quy trước khi bình luận.

0

maiemma đã bình luận lúc 27, Tháng 9, 2025, 15:16

ừ dễ mà

2

nam0610 đã bình luận lúc 25, Tháng 9, 2025, 13:31

vcl m đưa kiến thức đồ thị vô luôn à;)))

-1

abcnickname đã bình luận lúc 26, Tháng 9, 2025, 6:39

yep cho mấy em lớp 8 làm thậm chí mấy em lớp 6 còn làm được :>

2

Xpozy đã bình luận lúc 26, Tháng 9, 2025, 7:48

dễ mà