Problemas
오늘도 정올에서 학생들이 말썽을 피우며 자리에 앉아 있었고 화가 난 정 선생님은 또다시 벌을 주기로 하였다.
허나 저번처럼 벌을 주기엔 철기와 태현이가 머리를 써서 최소한도로 벌을 받는 방법을 만들었고, 이에 따라 다른 방식으로 벌을 주기로 하였다. 정 선생님은 이번에는 벌을 서는 시간을, 모든 학생이 움직인 총 합으로 벌을 주기로 하였다. 다시 말해서 3명의 학생이 자리에 위치할 때 각 3, 4, 5의 시간이 걸렸으면 총 12분의 벌을 받게 되는 것이다.
정올의 정보올림피아드 과정 강의실은 격자구조로 이루어져 있고, 각각의 칸마다 학생과 컴퓨터가 위치해 있다. 컴퓨터는 한 칸에 하나만 존재할 수 있으며, 학생의 경우 한 칸에 두 명 이상의 학생이 동시에 존재할 수 있다. 학생은 한 번에 상하좌우 한 칸으로 이동이 가능하며, 이동 할 때는 1의 시간이 걸린다. 컴퓨터가 있는 자리에 앉을 수 있는 학생은 한명밖에 없으며, 학생은 아무 컴퓨터에나 앉을 수 있다. 모든 학생들이 동시에 움직인다고 가정한다.
현재 정올학원의 강의실의 정보가 들어 올 때, 모든 학생이 컴퓨터가 있는 자리에 도착할 경우, 모든 학생의 이동한 시간의 합이 최소가 되게 출력하는 프로그램을 작성하라
Entrada
첫 번째 줄에는 강의실의 높이와 너비를 뜻하는 N, M(1≤N,M≤100)이 공백을 사이에 두고 입력된다.
그 다음 줄에는 N x M의 격자로 이루어진, 강의실의 정보가 입력이 된다. 한 개의 문자는 격자의 한 칸을 뜻하며, ‘.’은 비어있는 공간을 의미하고, 대문자 'C'는 컴퓨터가 있는 자리를 의미하며, 대문자 'S'는 개구쟁이 학생들을 의미한다. 컴퓨터의 대수와 학생의 명수는 같으며, 100이하이다.
Salida
모든 학생들이 도착하였을 때의 가능한 이동시간의 최소 값을 출력한다. 불가능한 경우는 없다고 가정한다.
Ejemplo
3 4
C..S
C..S
C..S
9
Debes iniciar sesión para escribir código.