05 August 2008
给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在 相同值 形成的环。
一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值 。
同时，你也不能回到上一次移动时所在的格子。比方说，环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。
如果 grid 中有相同值形成的环，请你返回 true ，否则返回 false 。
使用dfs来检测是否有环 有环的条件就是在搜索的过程中搜索到 该次 dfs已经访问过的坐标
定义一个二维数组记录以及访问过的坐标
考虑根据在搜索的过程中添加上一层搜索过来的方向，不搜索该方向的反方向
在这种情况下如果找到已经访问过的节点就说明有环，有环就直接返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
boolean[][] visited;
char[][] grid;
int m, n;
boolean hasRing;
public boolean containsCycle(char[][] grid) {
this.grid = grid;
m = grid.length;
n = grid[0].length;
visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j]) {
dfs(i, j, grid[i][j], 'L');
if (hasRing) return true;
}
}
}
return false;
}
private void dfs(int i, int j, char ch, char from) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != ch) {
return;
}
if (visited[i][j]) {
hasRing = true;
return;
}
visited[i][j] = true;
if (from != 'L') dfs(i, j - 1, ch, 'R');
if (from != 'R') dfs(i, j + 1, ch, 'L');
if (from != 'U') dfs(i - 1, j, ch, 'D');
if (from != 'D') dfs(i + 1, j, ch, 'U');
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public boolean containsCycle(char[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
Queue<int[]> queue = new LinkedList<>();
int[][] b = { {0, 1}, {1, 0}, {-1, 0}, {0, -1} };
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (!visited[i][j]) {
char ch = grid[i][j];
queue.add(new int[]{i, j});
while (!queue.isEmpty()) {
int[] a = queue.remove();
int row = a[0];
int col = a[1];
if (visited[row][col]) {
return true;
}
visited[row][col] = true;
for (int[] c : b) {
int nrow = row + c[0];
int ncol = col + c[1];
if (nrow < 0 || ncol < 0 || nrow >= rows || ncol >= cols || visited[nrow][ncol] || grid[nrow][ncol] != ch)
continue;
queue.add(new int[]{nrow, ncol});
}
}
}
}
}
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public boolean containsCycle(char[][] grid) {
int n = grid.length, m = grid[0].length;
UnionFind uf = new UnionFind(n * m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i + 1 < n && grid[i + 1][j] == grid[i][j]) { // connect to bottom
if (!uf.union(i * m + j, (i + 1) * m + j)) return true;
}
if (j + 1 < m && grid[i][j + 1] == grid[i][j]) { // connect to right
if (!uf.union(i * m + j, i * m + (j + 1))) return true;
}
}
}
return false;
}
class UnionFind {
int[] parent;
UnionFind(int sz) {
parent = new int[sz];
for (int i = 0; i < sz; i++) parent[i] = i;
}
boolean union(int a, int b) {
int par_a = find(a);
int par_b = find(b);
if (par_a == par_b) {
return false;
}
parent[par_a] = par_b;
return true;
}
int find(int a) {
if (a == parent[a]) return a;
return parent[a] = find(parent[a]);
}
}
}