BOJ 5368 Escape Route

문제 링크:

문제 내용

당신은 2차원 사각 격자의 s로 표시된 칸에 위치해 있습니다. 당신의 현재 위치에서 직선 거리로 가장 가까운 p의 위치를 구하세요. 두 칸 사이의 거리는 두 칸의 좌표 사이의 유클리드 거리로 정의합니다. 어떤 칸의 좌표는 (행 번호, 열 번호)로 정의합니다. 행 번호는 맨 윗줄을 0으로 두고, 열 번호는 맨 왼쪽 줄을 0으로 둡니다.

그러한 p가 여러 개라면, 행 번호가 가장 작은 것을 선택하고, 그러한 p도 여러 개라면 그 중에서 열 번호가 가장 작은 것을 선택합니다.

입력

첫 번째 줄에는 테스트 케이스의 개수 $T$가 주어집니다.

각 테스트 케이스에 대해, 격자의 크기 $m$이 주어지고, 다음 $m$줄에 걸쳐서 $m \times m$ 격자의 상태가 주어집니다. ($4 \le m \le 12$) 격자의 각 칸에 쓰여있는 글자는 s, p, w, - 중 하나입니다.

출력

각 테스트 케이스에 대해, s의 좌표를 $(r_s, c_s)$, 문제에서 묻는 p의 좌표를 $(r_p, c_p)$라고 할 때, ({r_s},{c_s}):({r_p},{c_p}):거리의 형식으로 출력합니다. 거리는 반올림하여 소수점 둘째 자리까지 출력합니다.

문제 풀이