비타로는 인테리어를 위하여 카펫을 구매했다. 카펫은 세로 H 행, 가로 W 열의 격자 모양으로 단락지어진 직사각형의 형태를 하고 있어 각 칸은 흰색 또는 검정색으로 염색 되어 있다. 카펫의 위에서 i 행째, 왼쪽에서 j 열째 ( 1 ≤ i ≤ H , 1 ≤ j ≤ W )에 있는 칸의 색은 문자열 S_i의 j 문자가 '.'이면 흰색, '#'이면 검은 색이다.

비타로는 카펫의 가장 왼쪽 상단 칸에 조각을 놓고 다음 조작을 여러 번 실시하여 그 조각을 카펫의 가장 오른쪽 아래 칸에 도달시키는 놀이를 생각했다.

조각이있는 칸과 색상이 다르며 상하 좌우에 인접한 칸을 하나 선택 하고 그 칸으로 조각을 이동시킨다.

비타로는 가장 오른쪽 아래 칸에 도달하는데 필요한 조작 횟수를 가능한 한 적게 하고 싶다. 그러나 카펫의 모양에 따라 도달 할 수 없을 수도 있다.

카펫 모양의 정보가 주어지면 조작을 반복하여 왼쪽 위의 칸에서 오른쪽 하단의 칸에 조각을 도달시킬 수 있는지를 판정하고, 가능하면 조작 횟수의 최소값을 구하는 프로그램을 작성하자.

#5855 upload 61 done 28 how_to_reg 28 call_split Subtask

카펫 (Carpet) timer 2s memory 1024MB

#5855
Subtask

카펫 (Carpet) 2s 1024MB