Sliding Puzzle on a Board with Fixed Pieces

In this problem, you are given a board with n rows and m columns. Each cell contains a chess piece of size \(1\times 1\) except one blank cell. Some pieces are fixed and cannot be moved, while others are movable. In one move, you may slide any movable piece that is adjacent (sharing an edge) to the blank cell into the blank cell (i.e. swap the positions of the piece and the blank).

The board itself (and thus the locations of fixed pieces) remains constant, but you will play q independent games. In the i-th game, the positions are given as follows (all positions are 1-indexed):

• Blank cell: \( (EX_i, EY_i) \)
• Designated movable piece: initial position \( (SX_i, SY_i) \)
• Target position for that piece: \( (TX_i, TY_i) \)

Your task is to compute the minimum number of moves needed to bring the designated movable piece to the target position, or output -1 if it is impossible.

How moves work:

A move means that if the blank is at cell \(B\) and a cell \(X\) which is adjacent to \(B\) is chosen, then you swap the contents of \(B\) and \(X\). Note that if \(X\) is the designated piece then it moves, otherwise only the blank changes its position. The positions of the fixed pieces never change and the movable pieces (aside from the designated one whose location you track) can be thought of as dummy tokens that simply allow blank motion on the board when swapped.

Note: Movement is only allowed between cells that are not fixed. In other words, fixed cells act as obstacles for the blank.

Mathematical formulation: We work on a grid of cells that are movable (i.e. not fixed). A move is allowed if the blank cell at \(b=(b_x,b_y)\) has an adjacent cell \(x=(x,y)\) (\(|b_x-x|+|b_y-y|=1\)) that is movable. There are two types of moves:

• If \(x\) holds the designated piece, then after swapping, the new state becomes \( (b', d') = (x, b) \).
• If \(x\) holds a dummy movable piece, then after swapping, the new state becomes \( (x, d) \) (the designated piece is not moved).

Your goal is to reach a state where the designated piece is at \( (TX_i, TY_i) \) in as few moves as possible.

inputFormat

The input begins with three integers \(n\), \(m\) and \(q\) \( (1 \leq n, m \leq 50,\; 1 \leq q \leq 1000)\) on one line, representing the number of rows, columns and the number of games respectively.

Then follow \(n\) lines, each containing \(m\) integers. Each integer is either 0 or 1. A 0 indicates that the cell is movable (i.e. it initially contains a movable piece), and a 1 indicates that the cell contains a fixed piece. Note that the board is fully occupied except for one blank cell which will be specified in each game.

After the board description, there are \(q\) lines. Each of these lines contains 6 integers: \(EX_i\) \(EY_i\) \(SX_i\) \(SY_i\) \(TX_i\) \(TY_i\). These represent, respectively, the row and column of the blank cell, the row and column of the designated movable piece, and the row and column of the target cell for the designated piece for the \(i\)-th game.

You may assume that in every query, the cell containing the designated piece and the target cell are movable (i.e. they are marked 0 in the board description).

outputFormat

For each game, output a single integer on a separate line – the minimum number of moves required to bring the designated piece to the target position, or -1 if it is impossible.

sample

3 3 3
0 0 0
0 1 0
0 0 0
2 1 1 1 1 2
1 3 3 3 3 1
3 1 2 1 2 3

7
-1
28

</p>