Springboards
플래티넘 I의견: 0
Bessie is in a 2D grid where walking is permitted only in directions parallel to
one of the coordinate axes. She starts at the point \((0,0)\) and wishes to reach
\((N,N)\) (\(1\le N\le 10^9\)). To help her out, there are \(P\) (\(1\le P\le 10^5\))
springboards on the grid. Each springboard is at a fixed point \((x_1,y_1)\) and
if Bessie uses it, she will land at a point
\((x_2,y_2)\).
Bessie is a progress-oriented cow, so she only permits herself to walk up or
right, never left nor down. Likewise, each springboard is configured to never go
left nor down. What is the minimum distance Bessie needs to walk?
Problem credits: Pedro Paredes
SCORING
- Test cases 2-5 satisfy \(P \le 1000\).
- Test cases 6-15 satisfy no additional constraints.
Problem credits: Pedro Paredes
The fist line contains two space-separated integers \(N\) and \(P\).
The next \(P\) lines each contains four integers, \(x_1\), \(y_1\), \(x_2\), \(y_2\),
where \(x_1 \le x_2\) and \(y_1 \le y_2.\)
All springboard and target locations are distinct.
Output a single integer, the minimum distance Bessie needs to walk to reach
\((N,N)\).
boards.inboards.out3 2
0 1 0 2
1 2 2 33Bessie's best path is:
- Bessie walks from (0,0) to (0,1) (1 unit).
- Bessie springs to (0,2).
- Bessie walks from (0,2) to (1,2) (1 unit).
- Bessie springs to (2,3).
- Bessie walks from (2,3) to (3,3) (1 unit).
The total walking length of Bessie's path is 3 units.
평가 및 의견
Springboards
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Springboards