forked from AnasImloul/Leetcode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Detect Cycles in 2D Grid.java
54 lines (46 loc) · 1.67 KB
/
Detect Cycles in 2D Grid.java
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
45
46
47
48
49
50
51
52
53
54
class Solution {
public boolean containsCycle(char[][] grid) {
int rows = grid.length, cols = grid[0].length;
// Create a boolean array of same dimensions to keep track of visited cells
boolean[][] visited = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (!visited[i][j] && dfs(grid, visited, i, j, 0, 0, grid[i][j])) {
return true;
}
}
}
return false;
}
public boolean dfs(
char[][] grid,
boolean[][] visited,
int i,
int j,
int prevI,
int prevJ,
char c
) {
// Check for out of bounds
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return false;
// Check whether the current char matches the previous char
if (grid[i][j] != c) return false;
// If we stumble upon the same cell, we're guaranteed to have found a cycle!
if (visited[i][j]) {
return true;
}
// Mark the cell as visited
visited[i][j] = true;
// We want to search in the south direction ONLY IF we didn't come from north
// Do the same for all four directions
boolean south = i - prevI != -1;
boolean north = i - prevI != 1;
boolean east = j - prevJ != -1;
boolean west = j - prevJ != 1;
return
(south && dfs(grid, visited, i + 1, j, i, j, c)) ||
(north && dfs(grid, visited, i - 1, j, i, j, c)) ||
(east && dfs(grid, visited, i, j + 1, i, j, c)) ||
(west && dfs(grid, visited, i, j - 1, i, j, c));
}
}