原文链接: https://leetcode-cn.com/problems/detect-cycles-in-2d-grid

英文原文

Given a 2D array of characters grid of size m x n, you need to find if there exists any cycle consisting of the same value in grid.

A cycle is a path of length 4 or more in the grid that starts and ends at the same cell. From a given cell, you can move to one of the cells adjacent to it - in one of the four directions (up, down, left, or right), if it has the same value of the current cell.

Also, you cannot move to the cell that you visited in your last move. For example, the cycle (1, 1) -> (1, 2) -> (1, 1) is invalid because from (1, 2) we visited (1, 1) which was the last visited cell.

Return true if any cycle of the same value exists in grid, otherwise, return false.

 

Example 1:

Input: grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
Output: true
Explanation: There are two valid cycles shown in different colors in the image below:

Example 2:

Input: grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
Output: true
Explanation: There is only one valid cycle highlighted in the image below:

Example 3:

Input: grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
Output: false

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 500
• grid consists only of lowercase English letters.

中文题目

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

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

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

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

 

示例 1：

输入：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
解释：如下图所示，只有高亮所示的一个合法环：

示例 3：

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

 

提示：

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

通过代码

高赞题解

思路

1. 从一个点开始， dfs 检测环
2. 需要一个记录当前 dfs 已经走过节点的 vector<vector<bool>> vi;
3. 不能走回头路，对上次来的格子要跳过
4. 如果走到了 vi 记录中，说明是环
5. 如果不是环，结束 dfs 时顺便把所有检测过的格子全部排除

答题

[]
class Solution {
public:
    bool containsCycle(vector<vector<char>>& grid) {
        g = grid;
        vi = vector<vector<bool>>(g.size(), vector<bool>(g[0].size(), false));

        for (int i = 0; i < g.size(); i++) {
            for (int j = 0; j < g[i].size(); j++) {
                if (g[i][j] == '.') continue;
                if (dfs(g[i][j], i, j, -1, -1)) return true;
            }
        }
        return false;
    }

    bool dfs(char c, int x, int y, int px, int py) {
        if (x < 0 || x >= g.size() || y < 0 || y >= g[0].size()) return false;
        if (g[x][y] != c) return false;
        if (vi[x][y]) return true;
        vi[x][y] = true;
        for (auto d : dd) {
            int dx = x + d[0];
            int dy = y + d[1];
            if (dx == px && dy == py) continue;
            if (dfs(c, dx, dy, x, y)) return true;
        }
        vi[x][y] = false;
        g[x][y] = '.';
        return false;
    }

private:
    vector<vector<char>> g;
    vector<vector<bool>> vi;
    vector<vector<int>> dd = { {0,1}, {0,-1}, {1,0}, {-1,0} };
};

致谢

感谢您的观看，希望对您有帮助，欢迎热烈的交流！

如果感觉还不错就点个赞吧~

这是 我的leetcode ，帮助我收集整理题目，可以方便的 visual studio 调试，欢迎关注，star

统计信息

通过次数	提交次数	AC比率
3882	10373	37.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言