解决方案

方法：螺旋形行走

思路

我们可以从开始的正方形开始，以螺旋形的形状行走，而忽略我们是否呆在网格中。最终，我们一定已经到达了网格的每一个角落。

算法

检查我们在每个方向的行走长度，我们发现如下模式：1，1，2，2，3，3，4，4，... 即我们先向东走 1 单位，然后向南走 1 单位，再向西走 2 单位，再向北走 2 单位，再向东走 3 单位，等等。因为我们的行走方式是自相似的，所以这种模式会以我们期望的方式重复。

之后，算法很简单：按照我们访问的顺序执行遍历并记录网格的位置。有关更多细节，请阅读内联注释。

复杂度分析

  • 时间复杂度：，潜在地，我们的行走需要螺旋式行进，直到我们向一个方向移动 ，向另一个方向移动 ，以便到达网格的每个单元格。

  • 空间复杂度：，答案用去的空间。