Solution:
Obviously it is a memory search. Obviously, the maximum distance that the current point can travel = the maximum distance of the next point+1.
The trouble with this problem lies in the code implementation. In the implementation process, the following points need to be paid attention to:
- When checking the cycle, it is not recommended to deal with it independently. Should be resolved together with the general situation. Otherwise, the time complexity will be multiplied by 2. Although it is a constant, the algorithm complexity is still $n^2$, but it is still relatively dangerous.
- If implemented in Java, it is recommended to avoid using recursive calls. Because the scale of $2000 \times 2000$ may cause stack overflow in Java.
- If implemented in C++, pay attention to memset. If the memory of [2000][2000] is allocated in advance, it will be very time-consuming if the memset is cleared every time.
- In C++, if you use objects (as in my code below), remember to use pointers all the way. Otherwise, the copying of the object will be time-consuming.
Others:
Personally do not recommend this problem. The reason is:
The idea of this problem is very obvious, so it is not enough to a problem which is more challenge the algorithm .
If this problem is focused on challenge the coding ability, it is actually very inappropriate. Because this problem will force the implementation to switch from the natural DFS code to stack code.
Therefore, I personally think that this problem is not good. Instead of find way to AC this problem, it is better to spend time on other better problems.
Code:
Java
C++
