二维网格图中探测环 图解题解

这道题到底在问什么

输入

grid=[["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]

输出

true

输入

grid=[["a","b","b"],["b","z","b"],["b","b","a"]]

输出

false

最优解：一步一步想明白

1. 3记牢这一句:撞上一个同字母、不是来处、又已经访问过的格子,就是环。下面从左上角 (0,0) 开始,顺着外圈的 a 一步步走,看这股搜索最后怎么绕回起点附近、把环兜住。
2. 4目标:找同字母的环舞台是一个 4 行 4 列的字母网格,外圈一整圈是字母 a,正中间 2 乘 2 是字母 b。我们要找的是:同一个字母能不能围成一条首尾相接、长度至少为 4 的环。规矩是一格一格走,只在相同字母之间挪动,而且不能马上退回上一步来的那格。盯着外圈这圈 a,它很可能就藏着一个环。
3. 5起点入栈从左上角 (0,0) 开始,它是 a、还没访问过,就以它为起点发起一次搜索,先把 (0,0) 标记成已访问。约定好规矩:只往上下左右走,目标格必须和当前格同字母,同时记住自己从哪一格来,等会儿靠它排掉假环。已访问 1 个。
4. 6上边出界先看 (0,0) 的上方,那里已经出了网格边界,外面没有格子,这个方向直接跳过。出界的方向不参与判断。
5. 7(0,1) 已访问看 (0,0) 右边的 (0,1),它是 a、和起点同字母又没访问过,踏进去,把它标记成已访问、压进待探索栈。已访问 2 个。
6. 8(1,0) 已访问再看 (0,0) 下方的 (1,0),同样是 a、没访问过,也踏进去标记入栈。此刻栈里排着 (0,1) 和 (1,0) 两个待探索的格子。已访问 3 个。
7. 9排掉来处 (0,0)弹出栈顶的 (1,0) 来扩展,它是从 (0,0) 下来的。看它上方正好是 (0,0),那就是刚刚来的那格、是上一步的来处,绝不能算成环,跳过这个方向。这条排除来处的规矩,正是用来挡掉走一步又退回去的长度 2 假环。
8. 10右边字母不同(1,0) 的右边是 (1,1),它是字母 b,和我们正在追的 a 不是同一个字母,走不过去,跳过。只在相同字母之间挪动。
9. 11(2,0) 已访问深度优先先弹出栈顶的 (1,0) 来扩展。它下方的 (2,0) 是 a、没访问过,踏进去标记入栈,顺着左边这一列继续往下探。已访问 4 个。
10. 12排掉来处 (1,0)轮到 (2,0) 扩展,它从 (1,0) 来。上方是 (1,0),又是来处,同样跳过。每到一格都先把来处这条路排掉,免得把回头路误当环。
11. 13右边字母不同(2,0) 的右边是 (2,1),它是字母 b,和我们正在追的 a 不是同一个字母,走不过去,跳过。只在相同字母之间挪动。
12. 14(3,0) 已访问从 (2,0) 往下走到 (3,0),它是 a、没访问过,踏进去标记。已访问 5 个,到了左下角,准备拐上底边。
13. 15(3,1) 已访问在 (3,0),上方是来处、下边和左边都出界,只剩右边的 (3,1),它是 a、没访问过,踏进去标记。已访问 6 个,沿底边往右推进。
14. 16(3,2) 已访问从 (3,1) 继续往右是 (3,2),a、没访问过,踏进去。已访问 7 个。
15. 17(3,3) 已访问从 (3,2) 往右走到 (3,3),a、没访问过,踏进去标记,这是右下角。已访问 8 个,接下来沿右列往上爬。
16. 18(2,3) 已访问在 (3,3),右边下边都出界,往上看 (2,3),是 a、没访问过,踏进去。已访问 9 个。
17. 19(1,3) 已访问从 (2,3) 往上是 (1,3),a、没访问过,踏进去标记。已访问 10 个,快爬到右上角了。
18. 20(0,3) 已访问从 (1,3) 往上走到 (0,3),a、没访问过,踏进去。已访问 11 个,到了右上角。
19. 21(0,2) 已访问在 (0,3),上边右边都出界,往左看 (0,2),是 a、没访问过,踏进去标记。已访问 12 个,十二个 a 已连成一长串,只差最后一步合龙。
20. 22排掉来处 (0,3)扩展 (0,2)。先看它右边的 (0,3),那正是我们刚从那儿过来的来处,按规矩跳过,这一步不能算环。
21. 23下边字母不同(0,2) 的下边是 (1,2),它是字母 b,和我们正在追的 a 不是同一个字母,走不过去,跳过。只在相同字母之间挪动。
22. 24环闭合,答案 true关键一步:看 (0,2) 左边的 (0,1)。它是 a、和当前格同字母,又不是我们的来处,可它早就被访问过了,正是最开始从 (0,0) 标记的那个 (0,1)。绕了外圈一整圈又撞回这个老格子,说明这串 a 首尾接上了,存在一个环,返回 true。
23. 25十二个 a 围成环回看全程:从 (0,0) 出发,顺着外圈的 a 一路标记,先沿左列下到 (3,0),再转底边、上右列、过顶边,最后 (0,2) 撞上早已访问的 (0,1),环就此闭合。判定一个环始终只看那一句话:走到一个同字母、又不是上一步来处、却已经访问过的格子。答案 true。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        m, n = len(grid), len(grid[0])
        vis = [[False] * n for _ in range(m)]
        dirs = (-1, 0, 1, 0, -1)
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if vis[i][j]:
                    continue
                vis[i][j] = True
                q = [(i, j, -1, -1)]
                while q:
                    x, y, px, py = q.pop()
                    for dx, dy in pairwise(dirs):
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < m and 0 <= ny < n:
                            if grid[nx][ny] != grid[i][j] or (nx == px and ny == py):
                                continue
                            if vis[nx][ny]:
                                return True
                            vis[nx][ny] = True
                            q.append((nx, ny, x, y))
        return False

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    bool containsCycle(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> vis(m, vector<bool>(n));
        const vector<int> dirs = {-1, 0, 1, 0, -1};

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!vis[i][j]) {
                    queue<array<int, 4>> q;
                    q.push({i, j, -1, -1});
                    vis[i][j] = true;

                    while (!q.empty()) {
                        auto p = q.front();
                        q.pop();
                        int x = p[0], y = p[1], px = p[2], py = p[3];

                        for (int k = 0; k < 4; ++k) {
                            int nx = x + dirs[k], ny = y + dirs[k + 1];
                            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                                if (grid[nx][ny] != grid[x][y] || (nx == px && ny == py)) {
                                    continue;
                                }
                                if (vis[nx][ny]) {
                                    return true;
                                }
                                q.push({nx, ny, x, y});
                                vis[nx][ny] = true;
                            }
                        }
                    }
                }
            }
        }
        return false;
    }
};

import java.util.*;
class Solution {
    public boolean containsCycle(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] vis = new boolean[m][n];
        final int[] dirs = {-1, 0, 1, 0, -1};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!vis[i][j]) {
                    Deque<int[]> q = new ArrayDeque<>();
                    q.offer(new int[] {i, j, -1, -1});
                    vis[i][j] = true;
                    while (!q.isEmpty()) {
                        int[] p = q.poll();
                        int x = p[0], y = p[1], px = p[2], py = p[3];
                        for (int k = 0; k < 4; ++k) {
                            int nx = x + dirs[k], ny = y + dirs[k + 1];
                            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                                if (grid[nx][ny] != grid[x][y] || (nx == px && ny == py)) {
                                    continue;
                                }
                                if (vis[nx][ny]) {
                                    return true;
                                }
                                q.offer(new int[] {nx, ny, x, y});
                                vis[nx][ny] = true;
                            }
                        }
                    }
                }
            }
        }
        return false;
    }
}

复杂度

面试官可能追问