This time we are going to play a Number Game.
The game is played on an
R x Cboard; rows are numbered 0 to R - 1 from top to bottom and columns are numbered 0 to C - 1 from left to right. The cell in row r and column c is said to have coordinates (r, c). Each cell of the board either contains a single-digit number (0 to 9) or is empty.
The board is given as R x C character array where the j-th character of the i-th element represents the cell at row i and column j; this element is a digit character ('0' - '9') if the cell contains the respective single-digit number or '.' if the cell is empty.
The goal of the game is to get from cell
(r1, c1)to cell
(r2, c2)with the fewest number of moves. A move is a jump of length d in a horizontal or vertical direction from a cell with a number d; more formally, if your position is (r, c) and the cell contains a number d, you can move to cell (r - d, c), (r + d, c), (r, c - d), or (r, c + d). Note that an empty cell or a cell with number 0 is a dead-end. You are also not allowed to leave the board at any time.
Furthermore, before performing moves you are allowed to write any single-digit numbers in at most
First Line contains denoting number of test cases.
Each test case begins with two integers on one line denoting R and C respectively.
Next R lines contains description of board each containing C characters.
Next Line contains 5 Integers denoting r1,c1,r2,c2 and K respectively.
Every Test cases gives the minimum number of moves required to do this if it is possible and print -1 instead.
0 0 2 3 0
0 0 2 3 1
Problem Setter : Arjun Singh Bhatia