shunfurh 于 2017.09.10 10:01 提问

The Erythea Campaign

O' mighty warrior,

Thy mission is to slay the foul king of Erythea.
Thou shall find him in his realm in the south.

God bless you,
After reading the order, you know you have a long, dangerous way down to the south, to find the king of Erythea in his realm and kill him. The Erythea realm is a rectangular region, with a number of horrible strongholds in it. Impenetrable walls enclose the region, so the only way for you to enter the realm is to fly by your Pegasus (flying horse) and land in some point in the region. The hiding place of the king is known so you just need to find your way to that location. As the area is extensive and covered by different terrain types, you have to travel on the grid-like roads in the region. The problem is, there are many guards on the towers of strongholds who can see you, and once seen, you have no chance to see your family again! The closer you travel to the strongholds, the greater the chances to be seen by the guards. The problem is to find the safest way from the point your Pegasus lands to the point where the king is.

Input

The input file consists of several test cases. The first line of the file contains a single number M, which is the number of test cases in the file (1 <= M <= 10). The rest of the file consists of the data of the test cases. Each test case data begins with a line containing the number of rows and the number of columns in the grid, which are in the range 1 to 80. The second line of a test case contains two pairs of integers, which are y and x coordinates of the source point (where the Pegasus landed) and the y and x coordinates of the destination point (where you may find the king). The horizontal and vertical lines in the grid are indexed from left to right and top to bottom from 0, so the coordinates can be expressed using these indices.

Following the first two lines, there are lines that describe the map of the region. Each line consists of a string of 0's and 1's, describing squares of the corresponding row. A 1 in the string tells you that the corresponding square in the grid belongs to a stronghold. The width of the region is the length of all strings, and its height in the number of strings.

Output

The output for each test case is the total risk of the minimum risk path from the landing point to the destination. Recall that the total risk of a path is sum of the risk levels of the points in the path (including source and destination). If no path exists between source and destination, the output should be 'no solution'. The output for each test case must be written on a separate line.

Sample Input

2
8 6
1 5 7 1
000000
011000
001000
000110
000110
000010
111000
000000
5 5
4 0 1 5
10000
10000
11111
00011
00001

Sample Output

149
101

1个回答

devmiao      2017.09.27 21:52