Codeforces Round #753 Robot on the Board 2 题解 (Java/C++)

题解

很明显是一个记忆化搜索。很明显，当前的点能走的最大距离=这一个点的下一个点的最大距离+1。

这个题的麻烦之处在于代码实现，在实现过程中，有以下几点需要注意：

1. 判断环的时候，不建议独立出来处理。应当和一般情况一并解决。否则时间复杂度会乘以2，虽然是个常数，算法复杂度仍然是$n^2$，但是还是比较危险。
2. Java实现的话，建议避免使用递归调用。因为$2000 \times 2000$的规模可能导致Java爆栈。
3. C++实现的话，要注意警惕memset。如果预先分配好[2000][2000]的内存，如果每次都memset清空的话会非常耗时。
4. C++的时候，如果有使用对象（就像是后面我的代码里那样），要记得全面使用指针。否则对象的复制也会比较耗时。

其他

个人不推荐这个题目。原因在于：
这个题目的思路非常明显，因此作为强调算法的题目来说是不够的。
如果这个题目作为移到考验编码能力的题目，其实也是非常不合适的。因为这道题目会迫使实现从自然的DFS写法转为手动维护堆栈。

因此，个人认为这个题目出的就很不好。于其研究怎么通过这个题，不如把时间花在其他题目上。

代码

Java

C++