공장탈출 timer 2s memory 512MB

석표는 N행 M열의 격자로 표현되는 준혁이의 문제 공장에서 일하고 있다.

모의고사 문제를 만들다 지친 석표는 마침내 문제공장을 탈출하기로 결심한다.

공장에는 여러가지 설비들이 있다.

W로 표현되는 칸은 벽이 있는 칸으로 석표가 지나갈 수 없는 칸이다.

반대로 . 으로 표현되는 칸은 아무것도 없는 빈칸이다.

C는 석표가 탈출하는지 감시하는 카메라를 의미한다.

카메라는 상하좌우 네 방향으로 거리 제한 없이 감시를 하며 석표는 카메라의 감시를 받는 칸을 지나면 걸리게 된다.

단, 카메라는 벽을 통과해서 감시를 하지는 못한다.

U, D, L, R은 각각 위쪽, 아래쪽, 왼쪽, 오른쪽으로 움직이는 컨베이어 벨트이다.

공장에서 생산된 문제를 나르는 컨베이어로, 석표가 이 위에 올라가면 이동 방향대로 강제로 움직이게 된다.

석표가 컨베이어 벨트 위에 올라가 있을때는 카메라의 감시를 받더라도 문제인척 하면 되기 때문에 걸리지 않는다.

컨베이어의 방향이 이상한 경우도 있어서 잘못 들어가면 벽에 끼이거나 영원히 벨트 위를 돌게 될 수도 있다.

S는 석표의 출발 위치를 의미한다.

석표는 한 번에 상하좌우중 한 방향으로 한 칸씩 움직일 수 있고, 벨트에 올라가면 내려오게 될 때까지 움직일 수 없다.

석표는 탈출을 결심하기는 했지만 출구가 어딘지는 모르기 때문에 모든 빈 칸까지 가는데 필요한 최소 움직임 수를 알고 싶다.

이때 컨베이어 벨트를 타고 움직이는 것은 횟수로 생각하지 않도록 하자.

불쌍한 석표를 위해 공장 지도를 받아 대신 계산해주도록 하자!​