Let's call a grid 8-puzzle board if the gridsize is 3 x 3 and there is exactly one cell is 'x' and others are '1' or '0'.
In one operation, you can exchange the 'x' cell of a 8-puzzle board with any cell which is adjacent to the 'x' cell. The cell (i, j) is adjacent to the cell (i-1, j), (i, j-1), (i, j+1) and (i+1, j) (if not out of bounds).
Now you are given N + 1 8-puzzle boards A1, A2, ..., AN and B. You need to answer how many 8-puzzle boards of A1, A2, ..., AN could be made into B in at most K operations.
Here are the N + 1 8-puzzle boards A1, A2, ..., AN and B of sample, where N = 4, K = 2.
0 x 0 0 0 0 0 0 0 0 0 1 0 x 0
1 0 1 1 x 1 0 1 1 1 0 x 1 0 1
0 0 1 0 0 1 x 0 1 0 0 1 0 0 1
A1 A2 A3 A4 B
A1, A2 and A4 could be made into B in K operations. The following show some feasible way to make them into B.
A way to make A1 into B in K operations:
0 x 0
1 0 1
0 0 1
A1 is as same as B in the beginning
A way to make A2 into B in K operations:
0 0 0 0 x 0
1 x 1 ========> 1 0 1
0 0 1 0 0 1
exchange (1,2)
A way to make A4 into B in K operations:
0 0 1 0 0 x 0 x 0
1 0 x ========> 1 0 1 ========> 1 0 1
0 0 1 0 0 1 0 0 1
exchange (1,3) exchange (1,2)
The first line contains two integers N and K – the number of 8-puzzle boards in A and the maximum number of operations you can execute for each 8-puzzle board.
Then you are given A1, A2, ..., AN and B in the order. All of them are in 3 lines of 3 characters. Please refer to Sample Input.
It's guaranteed that:
To pass testcase 7 and 8, note the efficiency of your strategy(code). It may be a little hard, so maybe you can try to solve other problems first after you pass first six testcases.
Output how many 8-puzzle boards of A1, A2, ..., AN could be made into B in K operations and then print a newline('\n').