1561 - Shortest Route
Time Limit : 2 Second
Memory Limit : 128 MB
Submission: 1
Solved: 1
- Description
- There are n grid points in a 2-Dimension plane, and m blocks in the plane, now alibaba require you to calculate each
pairofpoints’ distance. (the shortest one), notice the route you choose should only be the grid points(which means the
route from point A to point B is just comprised by grid points), and points can go just up, down, left, right. The route between
two points can not cross blocks but can along withblocks’ border.
(we ensure points will not be inside any blocks, and blocks may overlap)
- Input
- There are several test cases end with EOF
Each case started with two integers n, m. then followed by n lines indicates point’s coordinates formatted as x y. then m lines x1 y1 x2 y2 followed indicates there are m blocks whose upper left corner is (x1,y1), lower right corner is (x2,y2)
(x1 < x2, y2 < y1)
(1<=n<=50)
(1<=m<=50)
(|x|, |y| <= 2*10^9)
(|x1|, |x2|, |y1|, |y2|<=2*10^9)
All inputs are integer.
- Output
- An n*n matrix, the unit of ith row and jth column filled with the distance between ith point and jth point (by the points’ order in input), if point i can’t reach point j, then just fill -1.
- sample input
-
3 4 2 4 5 1 1 1 0 3 3 2 0 5 1 3 3 5 4 2 2 3 4 0
- sample output
-
0 8 6 8 0 6 6 6 0
- hint
- You can use this form of code to deal with several test cases.while (scanf(...) != EOF){//Your codes here.}orwhile (cin >> input){//your code here}
- source
- The 6th ACM Programming Contest of HUST