Quento

Quento는 Q42가 만든 게임이다. 게임판은 항상 3×3 크기이고, 위 그림처럼 검은 칸에는 숫자가, 흰 칸에는 + 또는 -가 적혀 있다. 행 번호와 열 번호의 합이 짝수인 칸이 숫자 칸, 홀수인 칸이 기호 칸이다.

게임판 위에는 만들어야 하는 수 N과 사용해야 하는 숫자의 개수 M이 주어진다. 숫자 칸에서 시작해 기호 칸으로 스와이프하고, 다시 숫자 칸으로 스와이프하는 식으로 이동한다. 스와이프는 상하좌우로 맞닿은 칸으로만 할 수 있고, 대각선으로는 갈 수 없다. 한 번 지난 칸은 다시 지날 수 없다. 이렇게 숫자 칸을 M개 지났을 때 계산 결과가 N이어야 한다.

계산은 왼쪽부터 차례대로 한다. 지나간 숫자를 순서대로 $a_1, a_2, \dots, a_M$, 기호를 $s_1, \dots, s_{M-1}$이라고 하면 $(((a_1 \, s_1 \, a_2) \, s_2 \, a_3) \dots) \, s_{M-1} \, a_M$의 값이 N이어야 한다. 중간 계산 값은 음수가 되어도 된다.

예를 들어 7을 숫자 2개로 만들려면 4+3이나 9-2가 가능하다. 5+3-1은 숫자를 3개 썼기 때문에 안 된다.

N과 M, 그리고 게임판에 적힌 숫자와 기호가 주어진다. 숫자 M개로 N을 만드는 방법을 구하는 프로그램을 작성하시오.

첫째 줄에 N과 M이 주어진다. ($1 \le N \le 45$, $2 \le M \le 5$) 둘째 줄부터 3개 줄에 걸쳐 게임판의 각 행이 길이 3인 문자열로 주어진다. 숫자는 항상 1 이상 9 이하의 한 자리 수이다.

숫자 M개로 N을 만들 수 있으면 첫째 줄에 1을, 만들 수 없으면 0을 출력한다.

만들 수 있으면 둘째 줄부터 $2M-1$개 줄에 걸쳐 지나간 칸의 좌표를 지나간 순서대로 한 줄에 하나씩 출력한다. 각 줄에는 행 번호와 열 번호를 공백으로 구분해 출력한다. 가장 왼쪽 윗칸의 좌표는 (0, 0), 왼쪽 아랫칸은 (2, 0), 오른쪽 윗칸은 (0, 2), 오른쪽 아랫칸은 (2, 2)이다.

만드는 방법이 여러 가지이면 좌표를 지나간 순서대로 늘어놓은 수열 $(r_1, c_1, r_2, c_2, \dots)$이 사전순으로 가장 앞서는 것 하나를 출력한다.

이 게임은 내려받아 직접 해 볼 수 있다.

http://quento.com/