题目描述

ZCC loves studying,so he rarely goes home. One day he suddenly wants to go home,so he gets information about the city and calculates the minimal time to go home(He can start at any time after time 0 or exactly at time 0), if he thinks the time isn't too long, he will go home. But going home will make ZCC spend less time on study, ZCC's teacher GPS doesn't want him to go home, so GPS controls all the traffic lights and they will never become green twice(That means when a light becomes red,it will never become green). At the beginning all the lights are red. As the end of the year is coming, in order to make the time shorter, ZCC can go through exactly one red light(Anyway, next year you will have 12 points again). But the problem becomes very hard and ZCC doesn't know how to calculate. He wants you to give him the answer. ZCC's city is very rich, so the traffic network forms a grid graph. On each intersection point(except the 4 corners) there are traffic lights. When the red light is on, ZCC can only turn right; When the green lights is on, ZCC can go straight, turn right, turn left or turn around as he like(ZCC can only turn around on intersection points). When ZCC starts from school, he can choose any direction to go(That is, the traffic light on the starting point can't affect him).

输入格式

There are multiple test cases end with EOF(no more than 10 test cases). The first line: two integers n,m indicating the size of ZCC's city's traffic network(2<=n,m<=20)  Next n lines each line contain m numbers, the i+1-th line's j-th number w1[i][j] indicating the first red light's end time of the point (i,j) Next n lines each line contain m numbers, the n+i+1-th line's j-th number w2[i][j] indicating the green light's end time of the point (i,j) (1<=w1[i][j]<=w2[i][j]<=2000000)(If w1[i][j] equals to w2[i][j], it means that the light is always red. Otherwise, in [ w1[i][j]+1, w2[i][j] ] the green light is on) (Because the corners don't have lights, you can ignore the value in the corners) Next n lines each line contain m-1 numbers, the 2n+i+1-th line's j-th number l1[i][j] indicating the length between point(i,j) and point(i,j+1) Next n-1 lines each line contain m numbers, the 3n+i+1-th line's j-th number l2[i][j] indicating the length between point(i,j) and point(i+1,j) (1<=l1[i][j],l2[i][j]<=100000) Next line contain 4 numbers sx,sy,tx,ty indicating the school's coordinate is (sx,sy) and home's coordinate is (tx,ty).

输出格式

Multiple test cases. Each test case output the minimal time to travel. If there's no solution, output -1.

0 0
0 0
0 0
0 0
1
2
3 5
1 1 2 2
4 3
0 1 0
1 1 1
8 1 1
0 9 0
0 1 0
1 1 1
9 1 1
0 99 0
1 1
1 1
1 1
1 1
9 4 1
1 1 1
1 1 1
1 2 4 3

Case #2: 8

提示

[Explanation of Sample 2] time 4:at (1,2) time 5:at (1,3) time 6:at (2,3) time 7:at (2,2) time 8:at (3,2)(7->8 run the red light) time 9:at (3,1) time 10:at (4,1) time 11:at (4,2) time 12:at (4,3) 12-4=8, so ZCC spends 8 time to go home.

题目来源

By 镇海中学