|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||1024 MB||10||4||4||40.000%|
Escaping from the police over city roofs is often tricky and the gangsters have to be trained properly. To keep up with current AI trends in criminality, they are developing a general computerized model of escape paths.
In the model, the city area where the escape happens is modeled as a 3D grid made of rectangular cuboids with square bases forming a 2D grid on flat ground. Each cuboid represents a block of houses. Top face of a cuboid is called a roof. In the model, all distances between adjacent blocks are reduced to 0. The path of escaping gangsters is modeled as a polyline – a sequence of straight horizontal and vertical segments where the end point of one segment is the start point of the next segment. The basic path properties are:
It may happen that two consecutive segments on the path share common points. This stems from the fact that the path models a real behavior of a person moving over physical obstacles. Thus an additional path rule also holds:
The total length of the escape path should be carefully calculated in the model.
The first line of the input contains six positive integers W, H, Sx, Sy, Ex, Ey (1 ≤ W · H ≤ 105, 1 ≤ Sx, Ex ≤ W, 1 ≤ Sy, Ey ≤ H). W and H are even integers representing the dimensions of the grid base in meters, integers Sx, Sy denote starting coordinates of the escape path and Ex, Ey denote coordinates of the end.
Each of the next H/2 lines contains W/2 integers, the i-th integer on j-th line is the height of the corresponding block Ti,j in meters (0 ≤ Ti,j ≤ 103). Each grid block base is a square with dimensions of 2 × 2 meters in the model.
Print the length of the escape path. The difference between the printed length and the exact length must be less than 10−4.
8 8 1 7 7 1 2 3 2 0 2 1 1 2 1 2 0 0 0 0 0 1
The sample input with its solution is shown on the picture above.