目标
给你一个二维字符网格数组 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 只包含小写英文字母。
思路
判断网格图中是否存在相同元素值形成的环，要求环的长度大于等于 4。沿着环移动总是能回到起点（沿着环顺时针或者逆时针移动，不能往回走，环中的元素只能访问一次）。
从每个格子出发 dfs，记录已访问的坐标 visited[i][j]，假设上一个访问的坐标 (px, py)，针对每一个格子枚举上下左右四个方向，下一个格子坐标为 (nx, ny)，如果不是 (px, py)，并且没越界且元素值相等，返回 visited[nx][ny] || dfs(nx, ny, x, y, visited, grid)。对于网格图，如果 (nx, ny) 不等于 (px, py) 并且已访问过说明存在环，并且环的长度至少是 4。
代码
/**
* @date 2026-04-26 23:14
*/
public class ContainsCycle1559 {
public static int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public boolean containsCycle(char[][] grid) {
int m = grid.length;
int 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(i, j, -1, -1, visited, grid)) {
return true;
}
}
}
return false;
}
public boolean dfs(int x, int y, int px, int py, boolean[][] visited, char[][] grid) {
int m = grid.length;
int n = grid[0].length;
visited[x][y] = true;
for (int[] d : directions) {
int nx = x + d[0];
int ny = y + d[1];
if ((nx != px || ny != py) && nx >= 0 && nx < m && ny >= 0 && ny < n && grid[x][y] == grid[nx][ny] &&
(
visited[nx][ny] || dfs(nx, ny, x, y, visited, grid)
)
) {
return true;
}
}
return false;
}
}
性能
