취미로 퍼즐을 즐기는 한 정올 학생이 더이상 풀 퍼즐이 없자, 새로운 퍼즐을 하나 만들었다.

이 퍼즐의 이름은 정사각형 퍼즐이다.

퍼즐 매니아 학생은 이 퍼즐을 택쌤에게 풀어보라고 했다.

택쌤은 대수롭게 않게 받아들였지만, 생각보다 너무 어려웠다.

그래서 택쌤은 퍼즐을 직접 푸는 대신, 퍼즐을 풀 수 있는 프로그램을 만드는 작업을 모의고사 문제로 내서, 여러분들이 택쌤의 일을 대신 하게 하려고 한다.

뭐 어쩔수 없다. 여러분들은 모의고사를 보는 중이니깐. 잔말말고 시원하게 풀어버리는 수밖에. 얼른 풀어서 택쌤의 코를 납작하게 만들도록 하자.

퍼즐은 N행 M열로 이루어진 2차원 보드판에서 진행된다.

보드판의 일부 칸은 사용하지 않는 칸이며, 남은 칸중에 K개의 칸은 "열쇠"를 포함하고 있다.

퍼즐 규칙은 간단하다. 보드판을 K개의 정사각형 영역으로 분할하되, 남는 영역이 없도록 해야 하고, 한 영역에 하나의 열쇠만 포함되게 하면 된다.

또한 어떤 정사각형 영역도 사용하지 않는 칸을 포함해선 안된다.

예를 들어 그림 1과 같은 경우는, 그림 2처럼 분할하는 것이 정답이다.

여기서 검정색 칸은 사용하지 않는 칸을 나타내며, 녹색은 열쇠를 나타낸다.

퍼즐의 초기상태가 주어졌을 때, 퍼즐의 해법을 출력하는 프로그램을 작성하라.

정사각형 퍼즐 timer 2s memory 256MB

정사각형 퍼즐 2s 256MB