가장 가까운 빈 운동 기구

문제

한 헬스장은 운동 공간을 같은 크기의 정사각형 칸으로 나누어 안내 지도를 만들었다. 지도는 H행 W열의 격자이며, 각 칸에는 벽, 통로, 출발 위치, 사용 가능한 운동 기구 중 하나가 표시되어 있다. 안내 단말기는 출발 위치에 있는 회원에게 가장 적게 이동하여 도착할 수 있는 운동 기구를 알려 주려고 한다. 회원은 현재 칸에서 위, 아래, 왼쪽, 오른쪽으로 붙어 있는 칸 중 하나로 이동할 수 있다. 한 번 이동할 때마다 이동 횟수가 1 증가한다. 대각선 이동은 할 수 없으며, 지도 밖으로 나가거나 벽이 있는 칸으로 들어갈 수 없다. 통로와 출발 위치, 운동 기구가 있는 칸은 모두 이동할 수 있는 칸이다. 운동 기구가 있는 칸에 들어갔다가 다시 나오는 것도 허용한다. 지도에는 추가로 열리는 문이나 방향에 따라 통행 여부가 달라지는 칸이 없다. 출발 위치에서 어떤 운동 기구까지의 거리는 허용된 이동만 사용하여 그 기구의 칸에 도착하는 최소 이동 횟수이다. 벽 때문에 도달할 수 없는 기구는 안내 대상에서 제외한다. 도달할 수 있는 기구가 하나 이상이면, 그중 가장 작은 거리를 구하고 그 거리를 갖는 운동 기구의 개수도 구해야 한다. 같은 기구로 가는 최단 경로가 여러 개여도 해당 기구는 한 번만 센다. 서로 다른 칸에 있는 기구는 각각 별개의 기구로 센다. 지도에는 출발 위치가 정확히 하나 있다. 사용 가능한 운동 기구는 하나도 없을 수 있으며, 기구가 있어도 모두 도달할 수 없는 곳에 있을 수 있다. 이러한 경우에는 거리를 -1, 기구의 개수를 0으로 출력한다. 가장 가까운 기구가 여러 개일 때 특정 기구 하나를 고르는 것이 아니라, 같은 최소 거리에 있는 모든 기구의 개수를 출력한다. 지도에서 출발 위치와 가장 가까운 운동 기구 사이의 거리 및 해당 기구 수를 계산하는 프로그램을 작성한다.

입력

첫째 줄에 정수 H와 W가 주어진다. 1≤H,W≤400이다.
다음 H개 줄에 길이가 W인 문자열이 주어진다. 각 문자는 벽을 뜻하는 '#', 통로를 뜻하는 '.', 출발 위치를 뜻하는 'S', 사용 가능한 운동 기구를 뜻하는 'E' 중 하나이다.
'S'는 전체 지도에 정확히 한 번 등장한다. 'E'의 개수에는 별도의 최솟값이 없다.

출력

가장 가까운 운동 기구까지의 최소 이동 횟수와 그 거리에 있는 기구의 개수를 공백으로 구분하여 출력한다. 도달할 수 있는 운동 기구가 없으면 -1 0을 출력한다.

3 5
E...E
..S..
.....

3 2

3 4
S#E.
##..
E...

-1 0

1 5
.SE.E

1 1

출처: Devin.KR 자체 제작