공주는 탈출할 수 있을까? timer 2s memory 512MB

어느 왕국에 폭정을 일삼던 공주가 시민 혁명에 궁을 떠나야 하는 처지에 놓였다. 시민군에 잡히면 평생을 감옥에서 살게 될 것이 분명하므로 확실한 탈출로를 찾아야 한다.

시민군이 궁안으로 들이닥쳤다. 마침 이런 경우를 대비하여 비상 출구를 한 곳 만들어 놓았다.

그런데 그 출구까지 가는 것이 문제이다. 시민군보다 먼저 도착하여야 한다.

편의상 궁을 N*M크기의 격자라고 하자. 또한 궁의 둘레에는 높은 성벽으로 가로 막혀있다고 한다.

공주의 수하들이 현재 시민군의 위치와 공주의 위치 등 탈출에 필요한 상태를 지도로 만들어 가지고 왔다. 이 지도를 토대로 공주가 확실하게 탈출할 수 있는 방법 존재하는지 판단하는 프로그램을 작성해보자.

지도 정보에는 아래 5가지 문자들만 입력된다는 것이 보장된다.     ‘@’ - 공주가 있는 현재 위치     ‘$’ - 시민군이 있는 위치     ‘%’ - 비상출구     ‘.’ - 지나갈 수 있는 공간     ‘#’ - 벽으로 막힌 곳 그리고 공주의 위치를 나타내는 문자 ‘@’와 비상출구의 위치를 나타내는 문자 ‘%’는 오직 한 개씩만 입력된다는 것이 보장된다.