오른손 법칙
시간 제한1초메모리 제한128 MB
미로의 각 입구에서 오른손 법칙을 따라 이동을 시뮬레이션하고, 목표를 밟거나 같은 행이나 열에서 바라볼 수 있는 입구의 수를 센다.
문제
정원 미로를 탐험하는 흔한 방법은, 미로에 들어서는 순간 입구의 오른쪽 벽에 손을 대고, 그 오른손을 항상 벽에 붙인 채 앞으로 걸어가는 것이다. 이것을 오른손 법칙이라고 한다.
이 방법으로 입구와 출구가 하나씩인 미로는 반드시 빠져나올 수 있다는 사실은 잘 알려져 있다. 하지만 미로 내부의 어떤 목표 지점에 도달해야 하는 경우에는 항상 성공하지는 않는다.
목표 지점 하나와 하나 이상의 입구가 표시된 미로가 주어진다. 각 입구에서 출발해 오른손을 벽에 붙인 채 걸을 때 목표를 찾을 수 있는지 판정하여라. 목표를 찾거나, 법칙을 따라 걷다가 어느 입구를 통해 미로 밖으로 다시 나가게 될 때까지 이동한다.
사람은 걸으면서 주위를 둘러보므로, 목표 칸을 직접 밟거나, 같은 행 또는 같은 열을 따라 벽에 가로막히지 않고 목표까지 일직선으로 볼 수 있는 칸에 도달하면 목표를 찾은 것으로 본다.
입력
입력은 하나 이상의 미로로 이루어진다. 각 미로는 두 정수 와 가 담긴 줄로 시작하며, 각각 미로의 너비와 높이를 뜻한다. 두 값 중 하나라도 보다 작으면 입력이 끝난다.
이어서 개의 줄이 주어진다. 각 줄에서는 처음 개의 문자만 의미가 있으며, 줄의 길이가 보다 짧으면 모자란 문자는 X로 간주한다.
각 문자의 의미는 다음과 같다.
G— 목표 지점인 빈 칸이며, 미로마다 정확히 하나 있다X— 벽E— 입구인 빈 칸이다. 모든 입구는 (와 로 정해지는) 미로의 바깥 테두리에 있으며, 어떤 두 입구도 서로 인접하지 않는다
모든 미로는 X와 E 문자로 완전히 둘러싸여 있다.
출력
각 미로에 대해 다음 형식의 한 줄을 출력한다.
The goal would be found from ? out of ? entrances.
첫 번째 ?는 오른손 법칙으로 목표를 찾을 수 있는 입구의 수로, 두 번째 ?는 전체 입구의 수로 바꾸어 출력한다.