Robot Đổi Hướng Trên Lưới
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề 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
-1nế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
Community Discussion