문제
요즘 준혁이는 미로 찾기 놀이에 한 참 열중이다. 준혁이가 알아낸 미로를 탈출 방법은 입구에서부터 왼쪽(또는 오른쪽) 벽만을 따라 가는 것이다.경로가 존재한다면 반드시 나갈 수 있다고 한다.
미로 찾기 놀이를 하던 중 준혁이는 궁금한 점이 생겼다. 어떤 미로에서 왼쪽 벽을 따라서만 이동했을 때, 오른쪽 벽을 따라서만 이동했을 때, 최단 거리로 이동할 때 방문하게 되는 격자의 개수는 얼마일까?
격자판 미로가 주어진다. ‘#’은 벽, ‘.’은 빈곳, ‘S’는 시작위치, ‘E’는 종료위치를 나타낸다. 탈출 경로는 항상 존재하며 상하 좌우로만 이동할 수 있으며 주어진 격자판 밖으로는 이동할 수 없다. 준혁이의 궁금증을 풀어주는 프로그램을 작성해보자.
입력
첫 행에 미로의 열과 행을 나타내는 정수 M, N (3 ≤ M, N ≤ 40) 이 주어진다. 이어 N개의 행에 미로정보가 주어진다. ‘#’은 벽, ‘.’은 빈곳, ‘S’는 시작위치, ‘E’는 종료위치를 나타낸다.
시작위치와 종료위치는 격자판의 테두리(꼭지점이 아닌)에 위치한다. 격자판의 테두리에는 '.'이 존재하지 않는다.
출력
하나의 행에 공백으로 구분하여 왼쪽 벽을 따라서만 이동했을 때, 오른쪽 벽을 따라서만 이동했을 때, 최단 거리로 이동할 때 방문하게 되는 격자의 개수를 출력한다.(중복 방문하는 경우와 S, E도 개수에 포함시킨다.)
예제
9 5
#########
#.#.#.#.#
S.......#
#.#.#.#.E
#########
18 16 10
출처
South Central USA 2006
로그인해야 코드를 작성할 수 있어요.