您所在位置：主题：[原创]A Simple Test
iytbdwt
[专家分：20] 发布于 2012-03-22 15:23:00
A Simple Test
--------------------------------------------------------------------------------
Time Limit: 2 Seconds Memory Limit: 65536 KB
--------------------------------------------------------------------------------
To celebrate the 10th anniversary of ZOJ, we are going to hold a simple test for our students, with a M*N rectangle containing some 1*1 blocks. The students are asked to select two blocks that have a "valid" path connecting each other. Then what does the word "valid" mean? Firstly, from one block, we can only go vertically or horizonally to another block. "valid selection" must conform to following constraints:
Both of the positions must have blocks.
They should NOT exist blocks on the path.
Only two chances of changing direction from vertical to horizonal or horizonal to vertical when advancing.
Path should NOT go outside rectangle.
For each student, he/she has an initial score of 60. If his/her selection is not valid, his/her score will be substracted by 1. If the selection is valid, his/her score will be added by 2 and the two selected blocks will both be removed. In both situations the test would continue. Notice that when next student come to test, he/she will face a new rectangle having no relationship with the former one.
Input
There are multiple cases. Each case is the input of one student. The first line describes total row number m and total column number n of the rectangle.(1 ≤ m ≤ 300 and 1 ≤ n ≤ 300)
The second line is the number of blocks b(2 ≤ b ≤ m*n)
Then following b lines describe row cooridinate and column cooridinate of blocks. If one (or two) of the blocks doesn't exist, student's score will be substracted by 1 without deleting the exist block.
After all above, there comes a line that contains the number of the student's inputs. The number is i.It's guaranteed i are non-negative number and will not exceed 1000.
Then following i lines are student inputs, containing the row cooridinate and column cooridinate of two chosen blocks.
Output
For each input in every case , calculate and output the student score step by step.
Sample Input
3 5
9
0 0
0 2
0 4
1 0
1 2
1 4
2 0
2 2
2 4
2
0 2 1 2
0 0 2 4
Sample Output
62
64
--------------------------------------------------------------------------------
Time Limit: 2 Seconds Memory Limit: 65536 KB
--------------------------------------------------------------------------------
To celebrate the 10th anniversary of ZOJ, we are going to hold a simple test for our students, with a M*N rectangle containing some 1*1 blocks. The students are asked to select two blocks that have a "valid" path connecting each other. Then what does the word "valid" mean? Firstly, from one block, we can only go vertically or horizonally to another block. "valid selection" must conform to following constraints:
Both of the positions must have blocks.
They should NOT exist blocks on the path.
Only two chances of changing direction from vertical to horizonal or horizonal to vertical when advancing.
Path should NOT go outside rectangle.
For each student, he/she has an initial score of 60. If his/her selection is not valid, his/her score will be substracted by 1. If the selection is valid, his/her score will be added by 2 and the two selected blocks will both be removed. In both situations the test would continue. Notice that when next student come to test, he/she will face a new rectangle having no relationship with the former one.
Input
There are multiple cases. Each case is the input of one student. The first line describes total row number m and total column number n of the rectangle.(1 ≤ m ≤ 300 and 1 ≤ n ≤ 300)
The second line is the number of blocks b(2 ≤ b ≤ m*n)
Then following b lines describe row cooridinate and column cooridinate of blocks. If one (or two) of the blocks doesn't exist, student's score will be substracted by 1 without deleting the exist block.
After all above, there comes a line that contains the number of the student's inputs. The number is i.It's guaranteed i are non-negative number and will not exceed 1000.
Then following i lines are student inputs, containing the row cooridinate and column cooridinate of two chosen blocks.
Output
For each input in every case , calculate and output the student score step by step.
Sample Input
3 5
9
0 0
0 2
0 4
1 0
1 2
1 4
2 0
2 2
2 4
2
0 2 1 2
0 0 2 4
Sample Output
62
64