텔레포트 탈출!
시간 제한1초메모리 제한128 MB
출구가 있는 격자 미로에서 각 단계마다 인접한 빈 칸으로 걷거나 열린 칸 중 하나로 무작위 순간이동할 수 있을 때, 출구에 도달하기까지 필요한 기대 걸음 수의 최솟값을 구한다.
문제
당신은 직사각형 미로 안에 있고, 가능한 한 적은 이동 횟수로 미로를 빠져나가려 합니다. 미로는 정사각형 칸으로 이루어진 격자이며, 일부 칸은 막혀 있고 일부 칸은 출구입니다. 출구 칸에 도착하는 순간 즉시 미로를 벗어납니다.
매 단계마다 다음 중 하나를 선택할 수 있습니다.
- 걷기: 현재 칸과 변을 맞댄 상·하·좌·우 네 칸 중 하나로 한 칸 이동합니다. 미로 바깥으로 나갈 수 없고, 막힌 칸으로도 이동할 수 없습니다.
- 텔레포트: 텔레포트 장치는 미로의 막히지 않은 모든 칸(지금 서 있는 칸 포함) 중에서 균등한 확률로 한 칸을 무작위로 골라 그곳으로 당신을 보냅니다. 도착한 칸이 출구라면 즉시 미로를 벗어납니다.
한 칸 걷는 것도 한 단계, 텔레포트를 한 번 쓰는 것도 한 단계로 셉니다. 미로를 벗어나는 유일한 방법은 (걸어서든 텔레포트로든) 출구 칸에 도달하는 것이며, 경계 밖으로는 결코 나갈 수 없습니다.
당신은 미로를 벗어나기까지 필요한 단계 수의 기댓값을 최소로 만들도록 최적으로 행동합니다. 이 최소 기대 단계 수를 구하세요.
입력
입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 두 양의 정수 과 (, )가 적힌 줄로 시작하며, 각각 행과 열의 개수입니다. 이어지는 개의 줄에는 미로의 한 행을 나타내는 정확히 개의 문자가 들어 있으며, 각 문자는 다음 중 하나입니다.
E— 출구. 모든 미로에는E가 적어도 하나 있습니다.Y— 당신의 시작 칸. 모든 미로에는Y가 정확히 하나 있습니다.X— 막힌 칸..— 빈 칸.
E, Y, .로 표시된 칸으로는 걷거나 텔레포트할 수 있습니다. 입력의 끝은 공백으로 구분된 두 개의 0이 적힌 줄로 표시됩니다.
출력
각 테스트 케이스마다, 최적으로 이동했을 때 미로를 벗어나는 데 필요한 최소 기대 단계 수를 한 줄에 출력하세요. 소수점 아래 정확히 셋째 자리까지 반올림하여 출력합니다. 답 사이에 빈 줄을 출력하지 마세요.