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

42

Đườ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