|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
B - Lazy Jumping Frog
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Mr. Frog lives in a grid-like marsh of rectangular shape, composed of equally-sized cells, some of which are dry, some of which are only watery places. Mr. Frog lives in a dry cell and can jump only from a dry cell to another dry cell on his wanderings around the marsh.
Mr. Frog wants to visit his girlfriend, Ms. Toad, who also lives in a dry cell in the same marsh. But Mr. Frog is lazy, and wants to spend the minimum amount of energy in his jumping way to Ms. Toad’s home. Mr. Frog knows how much energy he spends in any of his jumps. For any single jump, Mr. Frog always uses the following figure to determine which are the possible target cells from his current position (the cell marked $\texttt{F}$), and the corresponding energy spent in the jump, in calories. Any other cell is unreachable from Mr. Frog’s current position with a single jump.
Your task is to determine the minimum amount of energy that Mr. Frog needs to spend to get from his home to Ms. Toad’s home.
Input
The input contains several test cases. The first line of a test case contains two integers, $C$ and $R$, indicating respectively the number of columns and rows of the marsh $(1 \leq C, R \leq 1000)$. The second line of a test case contains four integers $C_f$ , $R_f$, $C_t$, and $R_t$, where $(C_f, R_f)$ specify Mr. Frog’s home location and $(C_t, R_t)$ specify Ms. Toad’s home location ($1 \leq C_f, C_t \leq C$ and $1 \leq R_f, R_t \leq R$). The third line of a test case contains an integer $W$ $(0 \leq W \leq 1000)$ indicating the number of watery places in the marsh. Each of the next W lines contains four integers $C_1$, $R_1$, $C_2$, and $R_2$ ($1 \leq C_1 \leq C_2 \leq C$ and $1 \leq R_1 \leq R_2 \leq R$) describing a rectangular watery place comprising cells whose coordinates $(x, y)$ are so that $C_1 \leq x \leq C_2$ and $R_1 \leq y \leq R_2$. The end of input is indicated by $C = R = 0$.
The input must be read from standard input.
Output
For each test case in the input, your program must produce one line of output, containing the minimum calories consumed by Mr. Frog to go from his home location to Ms. Toad’s home location. If there is no way Mr. Frog can get to Ms. Toad’s home, your program should output $\texttt{impossible}$.
The output must be written to standard output.
Sample test(s)
Input
4 4
1 1 4 2
2
2 1 3 3
4 3 4 4
4 4
1 1 4 2
1
2 1 3 4
7 6
4 2 7 6
5
4 1 7 1
5 1 5 5
2 4 3 4
7 5 7 5
6 6 6 6
0
Output
14
impossible
12