PHÁ TƯỜNG — ĐƯỜNG ĐI NGẮN NHẤT

Cho một mê cung gồm n hàng và m cột. Mỗi ô có một trong hai ký tự:

• .: Ô trống, có thể đi qua.
• #: Ô tường, bình thường không thể đi qua.

Bạn xuất phát từ ô (1, 1) và cần đi đến ô (n, m). Trong toàn bộ hành trình, bạn được phép phá tối đa một ô tường để đi vào ô đó. Việc phá tường không tốn thêm bước: di chuyển vào ô tường được phá vẫn tính là một bước.

Trong mỗi bước, bạn chỉ được di chuyển sang một ô kề cạnh theo bốn hướng: lên, xuống, trái hoặc phải. Không được đi ra ngoài mê cung và không được đi chéo.

Hai ô xuất phát và đích luôn là ô trống .. Bạn cũng được phép không phá tường nào nếu không cần thiết.

Yêu cầu: Hãy tìm số bước di chuyển ít nhất để đi từ ô (1, 1) đến ô (n, m). Nếu không tồn tại đường đi hợp lệ, in -1.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên n, m.
• n dòng tiếp theo, mỗi dòng gồm đúng m ký tự . hoặc #, biểu diễn mê cung.

Dữ liệu ra

In ra một số nguyên duy nhất: số bước ít nhất, hoặc -1 nếu không đến được đích.

Giới hạn

• 1 <= n, m <= 1000.
• n*m <= 1000000.
• Ô (1, 1) và ô (n, m) luôn là ..

Ví dụ 1

Input

3 3
.#.
##.
...

Output

4

Giải thích: Có thể đi theo (1,1) → (2,1) → (3,1) → (3,2) → (3,3). Ta phá ô tường ở (2,1) và đi tổng cộng 4 bước.

Ví dụ 2

Input

3 4
...#
.#.#
#.#.

Output

5

Giải thích: Một đường đi ngắn nhất là (1,1) → (1,2) → (1,3) → (2,3) → (3,3) → (3,4), trong đó phá ô (3,3). Đường đi có 5 bước.

Ví dụ 3

Input

3 3
.##
###
##.

Output

-1

Giải thích: Không thể tới đích nếu chỉ được phá tối đa một ô tường.

Phân nhóm điểm (100 điểm)