Robot Đổi Hướng Trên Lưới

Buổi 41 — SPFA & Bellman-Ford
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Một robot đứng tại ô (1, 1) của lưới kích thước N × M và muốn đi đến ô (N, M). Mỗi ô trên lưới chứa một ký tự hướng dẫn (U - lên, D - xuống, L - trái, R - phải) hoặc # (tường không thể đi vào). Khi đứng ở ô (r, c), nếu robot đi theo đúng hướng ghi trên ô (r, c) thì mất chi phí 0; nếu đi theo một trong 3 hướng còn lại thì mất chi phí 1. Hãy tìm chi phí nhỏ nhất để đến được (N, M).

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên N và M.
  • N dòng tiếp theo, mỗi dòng là một xâu độ dài M gồm các ký tự U, D, L, R, #.
Dữ liệu ra
  • Một số nguyên duy nhất là chi phí nhỏ nhất, hoặc -1 nếu không thể đến (N, M).
Ví dụ
Input Output
3 3
RRD
DLL
RRR
0
3 3
R#D
#RL
URR
-1
Giới hạn
  • 1 ≤ N, M ≤ 1000
Draft saved