Chơi golf

Xem dạng PDF

Gửi bài giải

Điểm: 100,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: GOLF.INP
Output: GOLF.OUT

Nguồn bài:
HNOI2223_R2
Dạng bài
Ngôn ngữ cho phép
C++, Pascal, Python

Một trò chơi đánh golf trên smartphone được mô phỏng là một lưới ô vuông có kích thước R dòng và C cột. Cho biết vị trí ô chứa bóng, vị trí ô chứa hố cần đánh bóng vào và vị trí của ô có vật cản. Tại mỗi lần chơi, người chơi có thể đánh quả bóng theo một trong bốn hướng (trên, dưới, trái, phải), quả bóng có thể di chuyển không quá K ô liên tiếp và không thể đi qua ô có vật cản.

Yêu cầu: Hãy tính số lần đánh bóng ít nhất để đưa được bóng vào hố.

Dữ liệu vào từ tệp văn bản GOLF.INP:

  • Dòng đầu tiên gồm ba số nguyên dương R,CK (R×C106; K106);
  • R dòng tiếp theo, mỗi dòng chứa C kí tự thuộc bốn loại kí tự sau:
    • . là vị trí ô trống;
    • # là vị trí ô có vật cản;
    • S là vị trí của bóng, có duy nhất một kí tự S trong bảng;
    • G là vị trí của hố, có duy nhất một kí tự G trong bảng.

Dữ liệu đảm bảo luôn có cách đưa bóng vào hố.

Kết quả ghi ra tệp văn bản GOLF.OUT:

Gồm một số nguyên duy nhất là số lần đánh bóng ít nhất cần thực hiện.

Ví dụ

Input
Copy
2 5 1
S#...
...#G
Output
Copy
7
Input
Copy
2 5 10
S#...
...#G
Output
Copy
5

Ràng buộc

  • 20% số test ứng với 20% số điểm không có kí tự # trong bảng;
  • 20% số test khác ứng với 20% số điểm có R2;
  • 20% số test khác ứng với 20% số điểm có R,C,K102;
  • 20% số test khác ứng với 20% số điểm có Kmax(R,C);
  • 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.