🔘 二维网格中探测环

📝 题目描述

给你一个二维字符网格数组grid，大小为m x n，你需要检查grid中是否存在相同值 形成的环。

一个环是一条开始和结束于同一个格子的长度 大于等于4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有相同的值。

同时，你也不能回到上一次移动时所在的格子。比方说，环(1, 1) -> (1, 2) -> (1, 1)是不合法的，因为从(1, 2)移动到(1, 1)回到了上一次移动的格子。

如果grid中有相同值形成的环，请返回true，否则返回false。

📋 代码模板

javatypescript

java

class Solution {
    public boolean containsCycle(char[][] grid) {

    }
}

typescript

function containsCycle(grid: string[][]): boolean {

}

💡 提示

$m == g r i d . l e n g t h$
$n == g r i d [i] . l e n g t h$
$1 \leq m \leq 500$
$1 \leq n \leq 500$
$g r i d$ 只包含小写英文字母

🚀 示例

示例一

输入grid为[['a','a','a','a'],['a','b','b','a'],['a','b','b','a'],['a','a','a','a']]，输出为true。该网格总共拥有 $2$ 个环，下图中用绿色标记出了这 $2$ 个环。

示例一

示例二

输入grid为[['c','c','c','a'],['c','d','c','c'],['c','c','e','c'],['f','c','c','c']]，输出为true。该网格总共拥有 $1$ 个环，下图中用绿色标记出了这 $1$ 个环。

示例二

示例三

输入grid为[['a','b','b'],['b','z','b'],['b','b','a']]，输出为false。该网格中不存在任何一个有效的环。

示例三

🖊️ 题解

一个合法的环必须符合特定要求：起始单元格和结束单元格必须是同一个格子。在这种情况下，满足这一条件的连通分量的大小至少为 $4$ ，即最小的环大小为 $4$ 。

最小环大小

因此，对于一个具有相同值的连通分量，只要保证其在被搜索时不走”回头路“，如果仍然能重复访问到同一单元格，那么该连通分量必定可以构成一个合法的环。

为了确保在连通分量搜索过程中不走”回头路“，我们可以把上下左右四个方向分别定义为两组互为相反数的整数。具体来说，”上“用 $- 1$ 表示，”下“用 $1$ 表示，”右“用 $- 2$ 表示，”左“用 $2$ 表示。这样一来，当上一个单元格朝 $d i r$ 方向移动至当前单元格，我们只需要保证接下去它不往 $- d i r$ 方向移动即可， $d i r$ 的值为 $- 1$ 、 $1$ 、 $2$ 或 $- 2$ 。

我们可以扫描整个二维网格，如果单元格尚未被访问过，则以它为起始节点进行DFS或BFS，起始节点需要在四个方向上都进行移动，此时 $d i r$ 可以设置为 $0$ 。在搜索过程中，我们需记录上一个单元格移动到当前单元格的方向 $d i r$ ，并确保当前单元格不往 $- d i r$ 方向移动，同时每遇到一个与起始节点值相同的单元格，则判断它是否已经访问过，如果已经访问过，应立即返回 $t r u e$ ，否则将该单元格标记为”已访问“状态。扫描结束，此时说明二维网格中不存在合法的环，应返回 $f a l s e$ 。

在本题中，我们需要额外使用一个m x n大小的 $v i s i t e d$ 数组，用于记录网格中的单元格是否被访问。

DFS

javatypescript

java

class Solution {
    private final static int START = 0, UP = -1, RIGHT = -2, DOWN = 1, LEFT = 2;
    private final static int[][] DIRS = new int[][]{{-1, 0, UP}, {1, 0, DOWN}
            , {0, -1, LEFT}, {0, 1, RIGHT}};

    public boolean containsCycle(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j]) {
                    continue;
                }
                if (dfs(grid, visited, i, j, grid[i][j], START)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] grid, boolean[][] visited, int i, int j
            , char value, int dir) {
        int m = grid.length, n = grid[0].length;
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || grid[i][j] != value) {
            return false;
        }
        if (visited[i][j]) {
            return true;
        }
        visited[i][j] = true;
        for (int d = 0; d < 4; d++) {
            if (DIRS[d][2] == -dir) {
                continue;
            }
            if (dfs(grid, visited, i + DIRS[d][0], j + DIRS[d][1]
                    , value, DIRS[d][2])) {
                return true;
            }
        }
        return false;
    }
}

typescript

const START = 0, UP = -1, RIGHT = -2, DOWN = 1, LEFT = 2;
const DIRS: number[][] = [[-1, 0, UP], [1, 0, DOWN]
    , [0, -1, LEFT], [0, 1, RIGHT]];

function containsCycle(grid: string[][]): boolean {
    const m = grid.length, n = grid[0].length;
    const visited: boolean[][] = Array.from({length: m}, () => Array(n).fill(false));
    let value: string;
    const dfs = (i: number, j: number, dir: number): boolean => {
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || grid[i][j] != value) {
            return false;
        }
        if (visited[i][j]) {
            return true;
        }
        visited[i][j] = true;
        for (let d = 0; d < 4; d++) {
            if (DIRS[d][2] == -dir) {
                continue;
            }
            if (dfs(i + DIRS[d][0], j + DIRS[d][1], DIRS[d][2])) {
                return true;
            }
        }
        return false;
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (visited[i][j]) {
                continue;
            }
            value = grid[i][j];
            if (dfs(i, j, START)) {
                return true;
            }
        }
    }
    return false;
}

BFS

javatypescript

java

class Solution {
    private final static int START = 0, UP = -1, RIGHT = -2, DOWN = 1, LEFT = 2;
    private final static int[][] DIRS = new int[][]{{-1, 0, UP}, {1, 0, DOWN}
            , {0, -1, LEFT}, {0, 1, RIGHT}};

    public boolean containsCycle(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) {
                    queue.offer(new int[]{i, j, START});
                    visited[i][j] = true;
                    while (!queue.isEmpty()) {
                        int[] cell = queue.poll();
                        int oldI = cell[0], oldJ = cell[1], dir = cell[2];
                        for (int d = 0; d < 4; d++) {
                            if (DIRS[d][2] == -dir) {
                                continue;
                            }
                            int currentI = oldI + DIRS[d][0], currentJ = oldJ + DIRS[d][1];
                            if (currentI < 0 || currentI > m - 1 || currentJ < 0 || currentJ > n - 1
                                    || grid[currentI][currentJ] != grid[i][j]) {
                                continue;
                            }
                            if (visited[currentI][currentJ]) {
                                return true;
                            }
                            queue.offer(new int[]{currentI, currentJ, DIRS[d][2]});
                            visited[currentI][currentJ] = true;
                        }
                    }
                }
            }
        }
        return false;
    }
}

typescript

const START = 0, UP = -1, RIGHT = -2, DOWN = 1, LEFT = 2;
const DIRS: number[][] = [[-1, 0, UP], [1, 0, DOWN]
    , [0, -1, LEFT], [0, 1, RIGHT]];

function containsCycle(grid: string[][]): boolean {
    const m = grid.length, n = grid[0].length;
    const visited: boolean[][] = Array.from({length: m}, () => Array(n).fill(false));
    const queue: number[][] = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (!visited[i][j]) {
                queue.push([i, j, START]);
                visited[i][j] = true;
                while (queue.length > 0) {
                    const cell: number[] = queue.shift()!;
                    const oldI = cell[0], oldJ = cell[1], dir = cell[2];
                    for (let d = 0; d < 4; d++) {
                        if (DIRS[d][2] == -dir) {
                            continue;
                        }
                        const currentI = oldI + DIRS[d][0], currentJ = oldJ + DIRS[d][1];
                        if (currentI < 0 || currentI > m - 1 || currentJ < 0 || currentJ > n - 1
                            || grid[currentI][currentJ] != grid[i][j]) {
                            continue;
                        }
                        if (visited[currentI][currentJ]) {
                            return true;
                        }
                        queue.push([currentI, currentJ, DIRS[d][2]]);
                        visited[currentI][currentJ] = true;
                    }
                }
            }
        }
    }
    return false;
}

💭 复杂度分析

基于DFS的解决方案的复杂度分析如下。

时间复杂度： $O (m n)$ 。其中 $m$ 与 $n$ 分别为网格的行数和列数。
空间复杂度： $O (m n)$ 。

基于BFS的解决方案的复杂度分析如下。

时间复杂度： $O (m n)$ 。其中 $m$ 与 $n$ 分别为网格的行数和列数。
空间复杂度： $O (m n)$ 。

🔘 二维网格中探测环 ​

📝 题目描述 ​

📋 代码模板 ​

💡 提示 ​

🚀 示例 ​

示例一 ​

示例二 ​

示例三 ​

🖊️ 题解 ​

DFS ​

BFS ​

💭 复杂度分析 ​

🔘 二维网格中探测环

📝 题目描述

📋 代码模板

💡 提示

🚀 示例

示例一

示例二

示例三

🖊️ 题解

DFS

BFS

💭 复杂度分析