뱀 게임

Google 버전의 Snake

뱀 게임은 고전 비디오 게임이다. 현대 미술관(MoMA)에 보존되어 있고, '역대 최고의 비디오 게임 100선'에 선정되었다. 게임의 목표는 뱀의 머리를 사과까지 옮기는 것이다. 뱀이 사과에 닿으면 사과를 먹고 몸이 길어진다. 그러면 새 사과가 놓이고, 길어진 뱀은 그 사과를 다시 먹어야 한다.

게임은 격자 위에서 진행되며, 뱀 몸의 각 칸은 격자의 한 칸을 차지한다. 머리는 세 방향으로 방향을 틀 수 있지만 뒤로 갈 수는 없다. 몸통은 머리를 따라간다. 머리가 몸통과 부딪히거나 격자 밖으로 나가서는 안 된다. 뱀 전체가 동시에 움직이므로, 머리는 꼬리가 막 비우는 칸으로 들어갈 수 있다.

이 게임에는 순발력과 선견지명이 필요하다. 뱀이 길어질수록, 머리가 사과에 닿기 전에 벽이나 자기 몸통에 부딪혀 죽을 수밖에 없는 방향으로 꺾기가 쉬워진다.

주어진 머리의 위치에서 머리가 사과에 도달할 수 있는지, 아니면 반드시 죽는지 판별하는 프로그램을 작성하라.

첫째 줄에 격자의 행 수 $r$과 열 수 $c$가 주어진다 ($1≤r,c≤10$, $r \cdot c≥2$).

다음 $r$개 줄에는 길이가 정확히 $c$인 문자열이 주어진다. 사용되는 문자는 '.', '0'부터 '9', 'a'부터 'f', 'A'이다. '.'은 빈 칸을 뜻한다. 16진수 숫자 '0'부터 '9'와 'a'부터 'f'는 뱀을, 'A'는 사과를 뜻한다.

뱀의 길이는 1칸 이상 16칸 이하이다. 머리는 '0'이고, 나머지 숫자는 '1', '2'처럼 순서대로 이어진다(숫자를 건너뛰지 않는다). 같은 숫자는 한 번만 나오며, '0'을 제외한 각 숫자는 바로 앞 숫자와 인접해 있다. 사과는 격자에 정확히 하나 있다.

정수 하나를 출력한다. 머리가 사과에 도달할 수 있으면 1을, 도달할 수 없어 반드시 죽으면 0을 출력한다.