24449번 - カーペット (Carpet) 서브태스크다국어

문제

オシャレ好きのビ太郎は,カーペットを新調した.カーペットは縦 H 行,横 W 列のマス目状に区切られた長方形の形をしており,各マスは白か黒のいずれかの色で塗られている.カーペットの上から i 行目,左から j 列目 (1 ≦ i ≦ H,1 ≦ j ≦ W) にあるマスの色は,文字列 S_i の j 文字目が . のとき白色,# のとき黒色である.

ビ太郎は,カーペットの最も左上のマスに駒を置き,以下の操作を何回か行うことで,その駒をカーペットの最も右下のマスに到達させるという遊びを思いついた.

• 駒が置かれているマスと色が異なり,かつ上下左右に隣接するマスを 1 つ選び,そのマスに駒を移動させる.

ビ太郎は,到達までの操作回数をなるべく少なくしたい.ただし,カーペットの模様によっては到達させられないかもしれない.

カーペットの模様の情報が与えられたとき,操作を繰り返すことで左上のマスから右下のマスに駒を到達させることが可能かを判定し,可能ならば操作回数の最小値を求めるプログラムを作成せよ.

입력

入力は以下の形式で標準入力から与えられる.

H W
S1
S2
:
SH

출력

操作を繰り返すことで左上のマスから右下のマスに駒を到達させることが可能な場合は操作回数の最小値を,不可能な場合は -1 を,標準出力に 1 行で出力せよ.

제한

• 1 ≦ H ≦ 500.
• 1 ≦ W ≦ 500.
• (H, W) ≠ (1, 1).
• S_i は長さ W の文字列である (1 ≦ i ≦ H).
• S_i の 各文字は . または # である (1 ≦ i ≦ H).
• H, W は整数である.

서브태스크

힌트