Cột trụ ma thuật

Cho một lưới hình chữ nhật gồm $n$ hàng và $m$ cột. Một số ô của lưới có đặt cột trụ, các ô còn lại để trống.

Một tia sáng di chuyển theo đường thẳng trong lưới. Khi gặp một cột trụ bình thường, tia sáng xuyên qua mà không đổi hướng. Ta có thể dùng phép thuật để biến một cột trụ thành cột trụ ma thuật: khi tia sáng chạm vào một cột trụ ma thuật, tia sáng được phản xạ đồng thời ra cả bốn hướng (lên, xuống, trái, phải) từ ô đó.

Tia sáng xuất phát từ cạnh phải của ô nằm ở góc dưới bên phải, tức ô $(n,m)$, và đi sang trái dọc theo hàng $n$. Cánh cửa nằm ở cạnh trái của ô ở góc trên bên trái, tức ô $(1,1)$.

Hãy tìm số cột trụ ít nhất cần yểm phép để tia sáng ra được khỏi cánh cửa, hoặc cho biết điều đó là không thể.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $n$ dòng tiếp theo, mỗi dòng gồm $m$ ký tự mô tả một hàng của lưới. Ký tự . là ô trống, ký tự # là ô có cột trụ.

Dữ liệu ra

In ra một số nguyên duy nhất là số cột trụ ít nhất cần yểm phép, hoặc $-1$ nếu không có cách nào để tia sáng ra khỏi cửa.

Ràng buộc

• $2\le n,m\le 1000$

Ví dụ