BGC TRUST IUPC 2012

Problem G

Balance the Blocks

Given a 4x4 grid, where every 1x1 cell contains (0 - 9) fixed and (0 - 8) moveable blocks. A block is a 1x1x1 cube. If a cell contains b blocks, those b blocks are stacked in 1 to b height (height 1 means touching the floor and height b means topmost block). If a cell contains both fixed and movable blocks, movable blocks will always stay on top of fixed blocks. There are at most 8 movable blocks in the grid.

Now we are playing a game on the given grid. Initially Player of the game will be at cell (x, y). If (x, y) contains some block then, player is on the top of the stack of blocks. At each move the player can do the following two things:

1. He moves to an adjacent reachable cell.

● Adjacent cells of a cell (x, y) are (x+1, y), (x, y+1), (x-1, y), (x, y-1).

● An adjacent cell of (x, y) is reachable if absolute difference of their stack height is at most 1. (Stack height = number of fixed blocks + number of movable blocks)

2. He can push and move the topmost movable block of an adjacent cell(X). After moving the block, he moves to the top of the stack at X. Pushed block moves onto the top of the stack of the neighboring cell(Y) of X in the same direction as it is pushed. The block cannot be moved outside the board. This operation can be performed if the following conditions are satisfied:

● Height of X is higher than the height of the stack on which the player is, by at most 2 and at least 1 (if height difference is two then the player will jump and push the adjacent block).

● Height of the stack containing the block(X) is greater than the height of the stack of target cell(Y).

Figure: (A) The player can jump up and down, (B) The player can push the box, (C) The player can jump and push the box

Output the minimum number of moves needed to make every positive height stacks equal. Two stacks are considered equal if their height is same.

Input

First line of input is an integer T (T <= 50) the number of test cases. For every test case first 4 x 4 grid represents the number of fixed blocks in the grid. Next 4 x 4 grid represents the number of movable blocks in the grid. Last line for each case contains two integers r and c representing the player position in the grid. Rows and columns are 0 indexed.

Output

For each test case print the number of test case “Case x:”. Here x is the number of test case. Then print a single integer which is the minimum number of moves to balance the blocks. If it is impossible to balance the blocks print “impossible”.

Sample Input	Output for Sample Input
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 3 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0	Case 1: 2 Case 2: 7

Problemsetter: Abu Obaida

Special Thanks: Md. Mahbubul Hasan