오른손 법칙

정원 미로를 탐험하는 흔한 방법은, 미로에 들어서는 순간 입구의 오른쪽 벽에 손을 대고, 그 오른손을 항상 벽에 붙인 채 앞으로 걸어가는 것이다. 이것을 오른손 법칙이라고 한다.

이 방법으로 입구와 출구가 하나씩인 미로는 반드시 빠져나올 수 있다는 사실은 잘 알려져 있다. 하지만 미로 내부의 어떤 목표 지점에 도달해야 하는 경우에는 항상 성공하지는 않는다.

목표 지점 하나와 하나 이상의 입구가 표시된 미로가 주어진다. 각 입구에서 출발해 오른손을 벽에 붙인 채 걸을 때 목표를 찾을 수 있는지 판정하여라. 목표를 찾거나, 법칙을 따라 걷다가 어느 입구를 통해 미로 밖으로 다시 나가게 될 때까지 이동한다.

사람은 걸으면서 주위를 둘러보므로, 목표 칸을 직접 밟거나, 같은 행 또는 같은 열을 따라 벽에 가로막히지 않고 목표까지 일직선으로 볼 수 있는 칸에 도달하면 목표를 찾은 것으로 본다.

입력은 하나 이상의 미로로 이루어진다. 각 미로는 두 정수 $w$와 $h$가 담긴 줄로 시작하며, 각각 미로의 너비와 높이를 뜻한다. 두 값 중 하나라도 $3$보다 작으면 입력이 끝난다.

이어서 $h$개의 줄이 주어진다. 각 줄에서는 처음 $w$개의 문자만 의미가 있으며, 줄의 길이가 $w$보다 짧으면 모자란 문자는 X로 간주한다.

각 문자의 의미는 다음과 같다.

• (공백) — 빈 칸
• G — 목표 지점인 빈 칸이며, 미로마다 정확히 하나 있다
• X — 벽
• E — 입구인 빈 칸이다. 모든 입구는 ($w$와 $h$로 정해지는) 미로의 바깥 테두리에 있으며, 어떤 두 입구도 서로 인접하지 않는다

모든 미로는 X와 E 문자로 완전히 둘러싸여 있다.

각 미로에 대해 다음 형식의 한 줄을 출력한다.

The goal would be found from ? out of ? entrances.

첫 번째 ?는 오른손 법칙으로 목표를 찾을 수 있는 입구의 수로, 두 번째 ?는 전체 입구의 수로 바꾸어 출력한다.