Lối thoát ngắn nhất

Bối cảnh và bài toán

Robot bảo trì di chuyển trong lưới nhà xưởng, bắt đầu tại A và cần tới B. Robot chỉ đi bốn hướng và không thể đi qua tường '#'.

Yêu cầu

Tìm số bước ít nhất từ A tới B; nếu không thể, in -1.

Input

Dòng đầu n, m; sau đó n dòng bản đồ chứa '.', '#', 'A', 'B'.

Output

In độ dài đường đi ngắn nhất hoặc -1.

Ràng buộc

• 1 <= n,m <= 1000 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n,m <= 30 | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

5 8
########
#.A#...#
#.##.#B#
#......#
########

Output

9

Giải thích. Mỗi bước có cùng chi phí 1 nên BFS trên các ô hợp lệ cho số bước nhỏ nhất.

Ví dụ 2

Input

3 3
A#B
###
...

Output

-1

Giải thích. Mỗi bước có cùng chi phí 1 nên BFS trên các ô hợp lệ cho số bước nhỏ nhất.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Labyrinth. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.