시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB86317813021.812%

문제

성호는 새로운 모바일 게임을 다운로드했다. 이 게임은 NxN 크기의 2차원 격자의 시작 지점에 있는 캐릭터를 조작해서 목표 지점까지 이동시키면 클리어되는 게임이다. 캐릭터의 상태는 일반 모드와 변신 모드, 2 가지다. 일반 모드일 때 캐릭터는 한 턴에 상하좌우 중에서 한 방향으로 한 칸 움직일 수가 있지만, 변신 모드라면 움직이는 방식이 달라진다. 

격자의 일부 칸에는 워프 지점이 있을 수가 있는데, 캐릭터가 변신 모드라면 한 턴에 캐릭터의 현재 칸을 기준으로 상하좌우 중 한 방향에 있는 가장 가까운 워프 지점으로 이동할 수만 있다. 만약 특정 방향에 워프 지점이 존재하지 않는다면 그 방향으로는 움직일 수 없다. 

일반 모드에서 변신 모드가 되는 데에는 t개의 턴이 소모되며, 변신 모드에서 일반 모드로 돌아가는 데에는 턴이 소모되지 않는다. 성호는 요즘 너무 바빠서 게임을 빨리 클리어하고 삭제해버리고 싶었다. 캐릭터가 최초에 1행 1열에 존재하며, 일반 모드인 상태일 때, 성호를 대신하여 게임을 클리어하는 데 필요한 최소 턴 수를 구해주자.

입력

첫 줄에 2차원 격자의 크기 N(1≤ N ≤ 500), 일반 모드에서 변신 모드로 변신하는 데 소모되는 턴의 수 t(0 ≤ t ≤ 500), 목표 지점의 행과 열의 번호 r(1 ≤ r ≤ N), c(1 ≤ c ≤ N)가 주어진다.

다음 줄에 2차원 격자의 워프 지점 정보가 N개의 줄에 걸쳐 주어진다. 각 줄은 N개의 문자로 이루어져 있으며, 각 문자는 '#' 이거나 '.' 이다. '#'는 워프 지점이 있는 칸을 나타내며, '.'는 워프 지점이 없는 평범한 칸을 나타낸다.

출력

게임을 클리어하는 데에 필요한 최소 턴 수를 출력한다.

예제 입력 1

3 1 1 3
.#.
...
...

예제 출력 1

2

예제 입력 2

3 0 3 3
...
...
#.#

예제 출력 2

2

힌트

예제 1에 대해, 일반 모드인 상태로 오른쪽으로 두 번을 이동하면 최소 턴 수이다.

예제 2에 대해, 맨 처음 일반 모드에서 변신 모드로 변신한 다음에 (3,1) 으로 이동한 뒤 (3,3) 으로 이동하면 최소 턴 수이다.