문제
레밍즈란, 화면안에 등장하는 수많은 레밍들을 출구까지 무사히 이동시키는 방식으로 진행되는 퍼즐 장르의 게임이다. 현재 게임의 화면을 입력받아 레밍이 출구 까지 도착 할 수 있는지 판단하는 프로그램을 작성하시오.
레밍의 갯수와 출구의 개수는 하나이다. 게임화면 밖은 모두 블록으로 꽉 차 있다고 가정한다.
만약 다음과 같은 경우 레밍은 D의 위치까지 움직일 수 있다. *는 움직이는 위치이다.
위의 경우들에서 볼 수 있듯, 레밍은 벽위에 있을때 평평할 경우, 그보다 블록이 한칸 위로 위치할 경우 움직임이 가능하다.
하지만 다음의 경우 레밍은 D의 위치까지 움직일 수 없다.
위에서 볼 수 있듯 막힌경우 올라갈 수 없을 경우 레밍은 목표지점에 다다를 수 없다.
또한 레밍이 움직이다 벽에 부딛혀서 더이상 갈 길이 없을 경우 레밍은 방향을 바꿔 이동한다.
이러한 규칙을 통해 레밍이 도착할 수 있을지 없을지 판단하는 프로그램을 작성하시오.
입력
게임화면의 높이(1≤H≤20)과, 게임화면의 너비(1≤W≤20)이 입력되어진다. 그러한다음 H * W 만큼의 문자로 게임화면이 입력되어지는데, 각각이 뜻하는 바는 다음과 같다. L : 현재 레밍의 위치, 처음의 레밍은 왼쪽을 향한다. . : 빈칸, 지면에 붙어있을 경우 이동이 가능하며, 빈칸의 바로 아래칸 역시 빈칸일 경우 레밍은 아래쪽으로 이동한다. D : 출구 # : 레밍이 움직일 수 없도록 방해하는 블록
출력
게임화면의 개수만큼 가능 여부를 출력한다. 만약 가능할 경우 'possible'을 출력하며, 그렇지 아니할 경우 'impossible' 을 출력한다.
예제 #1
4 4
L...
.##.
.#.D
...#
possible
예제 #2
5 5
L....
.....
....D
.....
....#
impossible
로그인해야 코드를 작성할 수 있어요.