변신 이동 게임

$N \times N$ 격자 위에서 캐릭터를 시작 칸에서 목표 칸까지 옮기는 게임이다. 캐릭터는 $(1, 1)$에서 일반 모드로 시작한다. 목표 칸은 $(r, c)$이다.

캐릭터는 일반 모드와 변신 모드 중 하나의 상태에 있다. 일반 모드에서는 한 턴에 상하좌우로 한 칸을 이동한다. 변신 모드에서는 한 턴에 현재 칸을 기준으로 상하좌우 중 한 방향을 골라 그 방향에서 가장 가까운 워프 지점으로 이동한다. 고른 방향에 워프 지점이 하나도 없으면 그 방향으로는 이동하지 못한다. 변신 모드에서는 워프 이동만 할 수 있다.

일반 모드에서 변신 모드로 바뀌는 데에는 $t$ 턴이 들고, 변신 모드에서 일반 모드로 돌아오는 데에는 턴이 들지 않는다. 시작 칸에서 목표 칸까지 도달하는 데 필요한 최소 턴 수를 구한다.

첫 줄에 격자 크기 $N$ $(1 \le N \le 500)$, 변신에 드는 턴 수 $t$ $(0 \le t \le 500)$, 목표 칸의 행 번호 $r$와 열 번호 $c$ $(1 \le r \le N, 1 \le c \le N)$가 공백으로 구분되어 주어진다.

이어지는 $N$줄에 워프 지점 정보가 주어진다. 각 줄은 $N$개의 문자로 이루어지며 각 문자는 # 또는 .이다. #는 워프 지점이 있는 칸을 뜻하고 .는 워프 지점이 없는 칸을 뜻한다.

목표 칸까지 도달하는 데 필요한 최소 턴 수를 한 줄에 출력한다. 걸어서만 이동해도 목표 칸에 도달할 수 있으므로 답은 항상 존재한다.

일반 모드 이동만으로 목표 칸에 도달할 수 있다. 변신은 워프 지점이 이어질 때 유리하고 되돌아오는 데 턴이 들지 않으므로 같은 칸에서 두 모드의 도달 턴을 함께 비교하면 된다. 현재 칸에 워프 지점이 있어도 워프 이동은 그 칸이 아니라 상하좌우에서 가장 가까운 워프 지점을 목적지로 삼는다.