Java方向网格循环查找：计算前置指令数与循环长度

你原来的方案仅能判断循环存在，核心问题是只标记了节点是否被访问过，没有记录每个节点第一次被访问时的步数，无法推导循环前长度和循环本身长度，以下是两种可行解法：

由于每个坐标点的下一跳是唯一的，我们只需要在遍历路径的过程中，用哈希表存储每个坐标(row, col)对应的首次访问步数即可，逻辑如下：

• 每走到一个新坐标，先检查是否已经在哈希表中存在
• 若不存在，将当前坐标和当前总步数存入哈希表，按照方向移动到下一个坐标，总步数+1
• 若已存在，说明找到循环起点：
  • 循环前的指令步数 = 该坐标在哈希表中存储的首次访问步数
  • 循环本身的指令步数 = 当前总步数 - 该坐标的首次访问步数

对应Java实现参考：

// 起始位置按题目要求给定，示例为(0,0)
int curRow = 0, curCol = 0;
int totalStep = 0;
// 哈希表key存储坐标，格式为"行,列"，value存储首次访问该坐标的步数
Map<String, Integer> visitedPos = new HashMap<>();

while (true) {
    String posKey = curRow + "," + curCol;
    // 命中已访问坐标，找到循环
    if (visitedPos.containsKey(posKey)) {
        int preCycleSteps = visitedPos.get(posKey);
        int cycleLength = totalStep - preCycleSteps;
        // 输出结果，也可根据需求返回
        System.out.println("循环前步数：" + preCycleSteps + "，循环长度：" + cycleLength);
        break;
    }
    // 记录当前坐标的首次访问步数
    visitedPos.put(posKey, totalStep);
    // 按方向移动
    char direction = grid.get(curRow).get(curCol);
    switch (direction) {
        case 'N': curRow--; break;
        case 'S': curRow++; break;
        case 'W': curCol--; break;
        case 'E': curCol++; break;
    }
    totalStep++;
}

该方法时间复杂度为O(nm)，空间复杂度为O(nm)，常规网格场景下性能足够，且不需要修改原网格数据。

如果网格规模极大，要求不使用额外存储，可以用弗洛伊德循环查找算法（龟兔赛跑法）实现：

• 第一步：慢指针每次走1步，快指针每次走2步，直到两个指针相遇，证明循环存在
• 第二步：将慢指针放回起始位置，快慢指针每次都走1步，再次相遇的位置就是循环的起点，此时走的步数就是循环前的指令步数
• 第三步：固定其中一个指针在循环起点，另一个指针每次走1步，直到回到起点，走的步数就是循环本身的指令步数

该方法不需要额外存储访问记录，空间复杂度为O(1)，仅需要多轮遍历即可得到结果。

内容的提问来源于stack exchange，提问作者ParkerHarrelson123