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

Submission #134325568 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #134328500 - Codeforces
Codeforces. Programming competitions and contests, programming community