Medium

题目描述

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

一个环是网格中长度 4 或更多 的一条路径，并且从同一个单元格开始和结束。从给定的单元格，你可以移动到 4 个方向上相邻的任何一个单元格（上、下、左、右），前提是目标单元格的 值与当前单元格的值相同。

同时，你不能沿着与上次移动 相反的方向 移动。例如，环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从 (1, 2) 移动到 (1, 1) 和上次移动相反。

如果网格中存在相同值形成的环，返回 true ，否则返回 false 。

示例 1：

输入：grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
输出：true
解释：如下图所示，有两个有效的环：

示例 2：

输入：grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
输出：true
解释：如下图所示，只有一个有效的环：

示例 3：

输入：grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
输出：false

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 500
  • grid 只包含小写英文字母。

解题思路

解题思路

这道题要求检测二维网格中是否存在由相同字符组成的环。我们可以使用深度优先搜索（DFS）来解决。

核心思想：

  1. 遍历网格中的每个位置作为起点进行DFS
  2. 在DFS过程中，记录访问过的位置和父节点（上一个位置）
  3. 对于当前位置的每个相邻位置：
    • 如果相邻位置字符相同且不是父节点，继续DFS
    • 如果相邻位置已被访问过且不是父节点，说明找到了环

关键点：

  • 使用 visited 数组记录已访问的位置
  • 记录父节点坐标，避免走回头路
  • 当遇到已访问的非父节点位置时，说明形成了环
  • 环的长度至少为4，这个条件通过不允许立即返回父节点来保证

算法步骤：

  1. 初始化访问标记数组
  2. 对每个未访问的位置开始DFS
  3. DFS中向四个方向探索，条件是字符相同
  4. 如果遇到已访问且非父节点的位置，返回true
  5. 如果所有位置都遍历完没有找到环，返回false

这种方法确保能检测到所有可能的环，时间复杂度合理。

代码实现

class Solution {
public:
    bool containsCycle(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) {
                    if (dfs(grid, visited, i, j, -1, -1)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
private:
    bool dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, 
             int x, int y, int px, int py) {
        visited[x][y] = true;
        
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (auto& dir : dirs) {
            int nx = x + dir[0], ny = y + dir[1];
            
            if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() 
                && grid[nx][ny] == grid[x][y]) {
                
                if (nx == px && ny == py) continue; // 跳过父节点
                
                if (visited[nx][ny]) return true; // 发现环
                
                if (dfs(grid, visited, nx, ny, x, y)) return true;
            }
        }
        return false;
    }
};

class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        
        def dfs(x, y, px, py):
            visited[x][y] = True
            
            for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                nx, ny = x + dx, y + dy
                
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == grid[x][y]:
                    if nx == px and ny == py:  # 跳过父节点
                        continue
                    
                    if visited[nx][ny]:  # 发现环
                        return True
                    
                    if dfs(nx, ny, x, y):
                        return True
            
            return False
        
        for i in range(m):
            for j in range(n):
                if not visited[i][j]:
                    if dfs(i, j, -1, -1):
                        return True
        
        return False

public class Solution {
    public bool ContainsCycle(char[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        bool[,] visited = new bool[m, n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i, j]) {
                    if (DFS(grid, visited, i, j, -1, -1)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
    private bool DFS(char[][] grid, bool[,] visited, int x, int y, int px, int py) {
        visited[x, y] = true;
        
        int[,] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int i = 0; i < 4; i++) {
            int nx = x + dirs[i, 0], ny = y + dirs[i, 1];
            
            if (nx >= 0 && nx < grid.Length && ny >= 0 && ny < grid[0].Length 
                && grid[nx][ny] == grid[x][y]) {
                
                if (nx == px && ny == py) continue; // 跳过父节点
                
                if (visited[nx, ny]) return true; // 发现环
                
                if (DFS(grid, visited, nx, ny, x, y)) return true;
            }
        }
        return false;
    }
}

var containsCycle = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    const visited = Array(m).fill().map(() => Array(n).fill(false));
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    function dfs(row, col, parentRow, parentCol, char) {
        visited[row][col] = true;
        
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && 
                grid[newRow][newCol] === char && 
                !(newRow === parentRow && newCol === parentCol)) {
                
                if (visited[newRow][newCol] || dfs(newRow, newCol, row, col, char)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (!visited[i][j]) {
                if (dfs(i, j, -1, -1, grid[i][j])) {
                    return true;
                }
            }
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(m × n)
空间复杂度O(m × n)

说明：

  • 时间复杂度：最坏情况下需要访问网格中的每个单元格一次，每次DFS的时间复杂度为O(1)
  • 空间复杂度：需要额外的visited数组存储访问状态，递归调用栈的深度最坏情况下为O(m × n)