Mô tả bài toán

Bitaro, một người yêu thích thời trang, vừa sắm một tấm thảm mới. Tấm thảm có hình chữ nhật được chia thành lưới gồm $H$ hàng dọc và $W$ cột ngang, mỗi ô được tô màu trắng hoặc màu đen. Màu của ô ở hàng thứ $i$ tính từ trên xuống và cột thứ $j$ tính từ trái sang ($1 \le i \le H$, $1 \le j \le W$) của tấm thảm là màu trắng khi ký tự thứ $j$ của xâu $S_i$ là ., và là màu đen khi ký tự đó là #.

Bitaro nghĩ ra một trò chơi như sau: cậu đặt một quân cờ ở ô trên cùng bên trái của tấm thảm, và thực hiện thao tác dưới đây một số lần để đưa quân cờ đến ô dưới cùng bên phải của tấm thảm.

• Chọn $1$ ô có màu khác với ô đang đặt quân cờ và kề cạnh (trên, dưới, trái, phải) với ô đó, rồi di chuyển quân cờ sang ô vừa chọn.

Bitaro muốn số lần thao tác để đến đích là ít nhất có thể. Tuy nhiên, tùy thuộc vào hoa văn của tấm thảm mà có thể không đưa được quân cờ đến đích.

Cho biết thông tin về hoa văn của tấm thảm, hãy viết chương trình kiểm tra xem có thể đưa quân cờ từ ô trên cùng bên trái đến ô dưới cùng bên phải bằng cách lặp lại thao tác trên hay không, và nếu có thể thì tìm số lần thao tác tối thiểu.

Ràng buộc

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ là xâu có độ dài $W$ ($1 \le i \le H$).
• Mỗi ký tự của $S_i$ là . hoặc # ($1 \le i \le H$).
• $H, W$ là các số nguyên.

Subtask

1. ($4$ điểm) $H = 1$.
2. ($14$ điểm) $H \le 5$, $W \le 5$.
3. ($24$ điểm) $H \le 30$, $W \le 30$.
4. ($58$ điểm) Không có ràng buộc bổ sung.

Dữ liệu vào

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

H W
S_1
S_2
:
S_H

Kết quả

Nếu có thể đưa quân cờ từ ô trên cùng bên trái đến ô dưới cùng bên phải bằng cách lặp lại thao tác, hãy in ra số lần thao tác tối thiểu; nếu không thể, hãy in ra -1 trên $1$ dòng ở đầu ra chuẩn.

Ví dụ

Ví dụ 1 - Dữ liệu vào

4 5
...#.
#####
...#.
#.###

Ví dụ 1 - Kết quả

9

Chẳng hạn, có thể xét các thao tác như trong hình vẽ.

Ở ví dụ bên trái, có thể đưa quân cờ từ ô trên cùng bên trái đến ô dưới cùng bên phải sau $9$ lần thao tác, còn ở ví dụ bên phải là sau $13$ lần thao tác.

Vì không thể đến đích với ít hơn $9$ lần thao tác, nên ta in ra $9$.

Ví dụ này thỏa mãn các ràng buộc của Subtask $2, 3, 4$.

Ví dụ 2 - Dữ liệu vào

3 3
...
...
...

Ví dụ 2 - Kết quả

-1

Cũng có trường hợp ngay từ đầu đã không thể thực hiện thao tác nào. Trong trường hợp này, vì không thể đưa quân cờ đến ô dưới cùng bên phải, nên in ra -1.

Ví dụ này thỏa mãn các ràng buộc của Subtask $2, 3, 4$.

Ví dụ 3 - Dữ liệu vào

1 5
.#.#.

Ví dụ 3 - Kết quả

4

Ví dụ này thỏa mãn các ràng buộc của tất cả các subtask.

Ví dụ 4 - Dữ liệu vào

5 5
###.#
.#...
.#..#
.####
##..#

Ví dụ 4 - Kết quả

12

Ví dụ này thỏa mãn các ràng buộc của Subtask $2, 3, 4$.

Ví dụ 5 - Dữ liệu vào

7 5
.#.##
##...
.#.##
.###.
##.#.
...#.
##.#.

Ví dụ 5 - Kết quả

12

Ví dụ này thỏa mãn các ràng buộc của Subtask $3, 4$.