요즘 준혁이는 미로 찾기 놀이에 한 참 열중이다. 준혁이가 알아낸 미로를 탈출 방법은 입구에서부터 왼쪽(또는 오른쪽) 벽만을 따라 가는 것이다.경로가 존재한다면 반드시 나갈 수 있다고 한다.

미로 찾기 놀이를 하던 중 준혁이는 궁금한 점이 생겼다. 어떤 미로에서 왼쪽 벽을 따라서만 이동했을 때, 오른쪽 벽을 따라서만 이동했을 때, 최단 거리로 이동할 때 방문하게 되는 격자의 개수는 얼마일까?

격자판 미로가 주어진다. ‘#’은 벽, ‘.’은 빈곳, ‘S’는 시작위치, ‘E’는 종료위치를 나타낸다. 탈출 경로는 항상 존재하며 상하 좌우로만 이동할 수 있으며 주어진 격자판 밖으로는 이동할 수 없다. 준혁이의 궁금증을 풀어주는 프로그램을 작성해보자.

미로 탈출 timer 1s memory 64MB

미로 탈출 1s 64MB