페레루로쉐를 좋아하는 찬효는
다른 초콜릿은 거들떠도 안보고 페레루로쉐만 즐기기로 유명합니다.
이를 괘씸하게 여긴 ABCD 초콜릿 나라의 공주가 찬효에게 저주를 걸어버렸습니다!!
저주에 걸린 찬효는 혀가 마비되어 ABCD 초콜릿이 아닌 초콜릿의 맛을 못 느끼게 되었습니다.
저주를 풀기 위해선 M
x N 크기로 나열되어있는 ABCD 초콜릿을 아래 조건에 맞게 먹어야 합니다.
(ABCD 초콜릿엔 특정 알파벳이 적혀있습니다.)
-
공주가 제시한 K개의 알파벳과 동일한 알파벳이 적혀있는 초콜릿을 순서를 맞춰 먹어야 합니다.
-
첫번째 초콜릿은 임의의 위치에서 먹을 수 있습니다.
-
하나의 초콜릿을 먹은 다음에는, 인접한 상하좌우에 있는 초콜릿만 먹어야 합니다.
-
이미 초콜릿을 먹었던 위치를 다시 지나갈 수 없습니다.
찬효는 ABCD 초콜릿을 너무나 먹기 싫었지만,
영영 페레루로쉐를 맛 볼 수 없는건 더 끔찍하게 생각하여
눈물을 머금고 저주를 풀기위해 심혈을 기울이기로 했습니다.
하지만 초콜릿 나라의 공주는 처음부터 순순히 저주를 풀어줄 생각이 없어서
저주를 풀 수 없도록 ABCD 초콜릿을 나열해 놓기도 했습니다.
찬효가 저주를 풀 수 있도록 초콜릿이 배열되어있는지 알려 주세요.