Given a grid maze with n rows and m columns, each cell is either an obstacle or has a cost associated. Your task is to go from (r1,c1) to (r2,c2) with minimum cost. In each step, you can go up, down, left or right, but not diagonally. Of course you cannot go into an obstacle or go out of the maze. The total cost of a path equals the sum of costs in each cell in the path. In the picture below, all shaded cells are obstacles. If you go along A → B → D → F → E, the cost is 10 + 3 + 6 + 14 + 8 = 41. Note that if you visit a cell twice, the cost is added twice. To make things more interesting, you need to answer an additional question: what if you must make a turn (left turn, right turn or U-turn) in each step. For example, if you go from A to B in the first step, you can go from B to D or A, but not G. In the example above, the best route is A → B → D → H → D → F → E, the total cost is 10+3+6+2+6+14+8 = 49. Note that D is visited twice. Input There will be at most 10 test cases. Each test case begins with a line containing six integers n, m, r1, c1,r2,c2 (2≤n,m≤500,1≤r1,r2 ≤n,1≤c1,c2 ≤m). Thenextnlinesdescribethemaze. Each cell is either a positive integer between 1 and 100 or an asterisk ‘*’. Note that neither the starting cell nor the ending cell can be an obstacle. Output For each test case, print the case number and two integers, the first one is the answer to the “normal case”, and the next one is the answer to the “interesting case”. If there is no route in either case, the corresponding integer should be ‘-1’. Sample Input 441232 7 10 3 9
45 6 2
8 14 * 21 1 * * 241114 1234 9**9 241114 134 999
2/2 Sample Output Case 1: 41 49 Case 2: 10 -1 Case 3: -1 -1