Hô hô hô, ông già Noel đã đến nhà các bạn trẻ rồi đây. Nhưng mà nhà ở Việt Nam thì làm sao có ống khói đúng không nè? Vì vậy để phát quà, ông già Noel sẽ phải phát quà bằng cách đi vào từ cửa trước của căn nhà, đến đặt quà ở cây thông Noel trong nhà rồi thoát ra ở cửa sau.
Căn nhà được mô tả bằng một bảng hình chữ nhật kích thước ~m\cdot n~, gồm ~m~ hàng được đánh số ~1 \to m~ và ~n~ cột được đánh số ~1\to n~. Ô ở hàng ~i~ cột ~j~ được kí hiệu là ô ~(i, j)~. Các ô được mô tả bằng các kí tự sau:
.
: Sàn nhà. Ở vị trí này ông già Noel có thể đi qua được.#
: Bức tường. Ông già Noel không thể đi qua ô này được.A
: Vị trí của cây thông Noel. Dữ liệu vào đảm bảo tồn tại đúng ~1~ cây thông Noel trên bảng.
Ngoài ra, cửa trước của các căn nhà được đặt tại ô ~(1, 1)~, cửa sau tại ô ~(m, n)~ và tại các vị trí này đảm bảo không có tường. Khi ông già Noel ở các ô ~(i, j)~ có kí tự .
hoặc A
, ông già có thể di chuyển sang các ô chung cạnh ~(i+1, j), (i, j+1), (i-1, j), (i, j-1)~, với điều kiện những ô đó đi qua được và không vượt qua rìa của bảng.
Vì ông già Noel phải đi phát quà cho rất nhiều trẻ em nên việc phát quà ở từng ngôi nhà phải diễn ra càng nhanh càng tốt. Các bạn hãy giúp ông già Noel tìm một đường đi từ cửa trước, đến cây thông để đặt quà, rồi thoát ra cửa sau sao cho ông già đi qua số lượng ô là ít nhất nhé.
Input
- Dòng đầu tiên chứa hai số nguyên ~m, n~ - kích thước của bảng kí tự mô tả căn nhà mà ông già Noel đến phát quà;
- ~m~ dòng tiếp theo, mỗi dòng chứa một xâu độ dài ~n~ chỉ gồm các kí tự
.
,A
và#
.
Output
- In ra trên một dòng duy nhất là số lượng ô nhỏ nhất mà ông già Noel phải đi qua để phát quà cho căn nhà này. Nếu ông già Noel không thể phát quà theo kế hoạch trên, bạn hãy in ra ~-1~.
- Lưu ý: Khi ông già Noel đi vào một ô đã đi qua trước đó, thì ta vẫn xem là ông đi qua ~2~ ô.
Giới hạn
- Subtask ~1~: ~50\%~ số test có ~m, n \le 5~;
- Subtask ~2~: ~50\%~ số test còn lại có ~m, n \le 2000~.
Sample Input 1
5 3
.#.
..A
#..
..#
...
Sample Output 1
9
Sample Input 2
5 3
.#.
...
#A.
..#
.#.
Sample Output 2
-1
Bình luận