March

During a game of Civilization V, much of your time will be spent moving units around the world. You'll be marching your army units off to discover stuff or to fight with your neighbors.

The world is comprised of hexagons. Generally, units move from hexagon to hexagon, paying the "Movement Cost" required to enter the new hexagon.
Movement Points:
All army units have a certain number of "Movement Points"(MPs) that they can expend on movement in every turn. Once they've expended those MPs, they can't move any more until the next turn.
Expending MPs:
Units expend MPs to enter tiles. The terrain of the tile determines the MP cost of the move. It doesn't cost anything to leave your current tile; the MP cost is determined by the tile you're entering.
A unit can always move one tile if it has any MPs left.It doesn't matter how expensive the tile is; as long as the unit has some MPs left, it can enter.
Terrain of the tile:
Open terrain like Grassland and Plains cost 1 MP to enter, while Forest and Jungle costs 2.
Zones of Control:
Enemy units exert a "Zone of Control"(ZOC) over the tiles around them. When a unit moves between two tiles within enemys' ZOC it expends all of MPs.(you can't move on the tile which contain an enemy)
Road:
As long as the unit moves from one tile containing a road into another tile containing a road,the unit will expend just 0.25 MPs no matter what terrain of the tile.(unless within an enemy's ZOC)
Rivers:
Rivers are between two tiles.
As long as the unit moves cross a rivers from a tile to another tile it expends all of MPs(unless these tiles contain roads).

Giving the information of the World, please tell me the minimum turns to cost for reaching the destination.

The first line is a number T(1<=T<=30), represents the number of case. The next T blocks follow each indicates a case.
The first line of each case contains three integers N, M(2<=N,M<=100), indicating the size of World, and MP(1<=MP<=10).
Then N lines follow, each line contains M integers.
Each module number tells the information of the tile and is the sum of up to ten integers:
1: Grassland and Plains
2: Forest and Jungle
4: Road
8: Enemy
16: A river on northeast of the tile
32: A river on east of the tile
64: A river on southeast of the tile
128: A river on southwest of the tile
256: A river on west of the tile
512: A river on northwest of the tile
(each tile must contain either 1 or 2)
Then a line with two coordinates x1,y1,x2,y2(0<=x1,x2<n,0<=y1,y2<m) indicating the source and destination. There is no enemy in source and destination and source is different from destination.
The picture below shows the coordinate of the World.

For each case, output the number of case and the minimum turns to cost for reaching the destination.If can't reach the destination, just output -1.(as shown in the sample output)

3
2 2 10
97 257
513 1
0 0 1 1

2 2 1
101 262
513 2
0 0 1 1

3 3 2
5 5 5
10 10 5
1 1 5
0 0 2 2

Case 1: 2
Case 2: 1
Case 3: 4

Case 1: (0,0)->(0,1)->(1,1)
First turn cross a river, you expends all of MPs. So you need waiting second turn to reach (1,1)
Case 2: (0,0)->(0,1)->(1,1)
There are roads on these tiles, so you cross the river expends 0.25 MPs, then expends the remain MPs to reach (1,1).
Case 3: (0,0)->(0,1)->(0,2)->(1,2)->(2,2)
Even if there are roads on these tiles, but there are all in ZOC, so you will expends all of MPs each move.

NotOnlySuccess

2011 Alibaba Programming Contest