Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1559.html
Solution 1. DFS
We can use DFS for each A[x][y] to see if we can form a circle from A[x][y].
Let seen[x][y] be the length of the sequence containing the same character ending with A[x][y].
In the DFS, assume the next location we want to visit is <a, b>.
We shouldn’t visit a, b if either of these is true:
a, bare out-of-bound.A[a][b] != A[x][y]seen[a][b] != 0andseen[x][y] - seen[a][b] < 3, meaning that we’ve visitedA[a][b]in the sequence and the distance betweenA[a][b]andA[x][y]is too small to form a valid circle.
Once we find a <a, b> pair satisfying seen[a][b] && seen[x][y] - seen[a][b] >= 3, we’ve found a valid circle from A[a][b] to A[x][y] with length more than or equal to 4, and we can return true.
// OJ: https://leetcode.com/problems/detect-cycles-in-2d-grid/
// Time: O(MN)
// Space: O(MN)
class Solution {
int seen[501][501] = {}, M, N, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
bool dfs(vector<vector<char>> &G, int i, int j, int len = 1) {
seen[i][j] = len;
for (auto &[dx, dy] : dirs) {
int x = i + dx, y = j + dy;
if (x < 0 || x >= M || y < 0 || y >= N || G[x][y] != G[i][j] || (seen[x][y] && seen[i][j] - seen[x][y] < 3)) continue;
if (seen[x][y] && seen[i][j] - seen[x][y] >= 3) return true;
if (dfs(G, x, y, len + 1)) return true;
}
return false;
}
public:
bool containsCycle(vector<vector<char>>& G) {
M = G.size(), N = G[0].size();
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (seen[i][j]) continue;
if (dfs(G, i, j)) return true;
}
}
return false;
}
};
Solution 2. DFS
// OJ: https://leetcode.com/problems/detect-cycles-in-2d-grid/
// Time: O(MN)
// Space: O(MN)
class Solution {
int seen[501][501] = {}, M, N, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
bool dfs(vector<vector<char>> &G, int i, int j, int prevX, int prevY) {
if (seen[i][j]) return true;
seen[i][j] = 1;
for (auto &[dx, dy] : dirs) {
int x = i + dx, y = j + dy;
if (x < 0 || x >= M || y < 0 || y >= N || G[x][y] != G[i][j] || (prevX == x && prevY == y)) continue;
if (dfs(G, x, y, i, j)) return true;
}
return false;
}
public:
bool containsCycle(vector<vector<char>>& G) {
M = G.size(), N = G[0].size();
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (seen[i][j]) continue;
if (dfs(G, i, j, -1, -1)) return true;
}
}
return false;
}
};
-
class Solution { int rows; int columns; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; boolean flag = false; public boolean containsCycle(char[][] grid) { rows = grid.length; columns = grid[0].length; if (rows < 2 || columns < 2) return false; boolean[][] visited = new boolean[rows][columns]; for (int i = 0; i < rows && !flag; i++) { for (int j = 0; j < columns && !flag; j++) { if (!visited[i][j]) depthFirstSearch(grid, visited, i, j); } } return flag; } public void depthFirstSearch(char[][] grid, boolean[][] visited, int row, int column) { visited[row][column] = true; char c = grid[row][column]; int value = row * columns + column; for (int[] direction : directions) { int newRow = row + direction[0], newColumn = column + direction[1]; if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && grid[newRow][newColumn] == c) { int key = newRow * columns + newColumn; if (!visited[newRow][newColumn]) { map.put(key, value); depthFirstSearch(grid, visited, newRow, newColumn); } else if (map.getOrDefault(value, -1) != key) flag = true; } } } } ############ class Solution { private int[] p; public boolean containsCycle(char[][] grid) { int m = grid.length; int n = grid[0].length; p = new int[m * n]; for (int i = 0; i < p.length; ++i) { p[i] = i; } int[] dirs = {0, 1, 0}; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < 2; ++k) { int x = i + dirs[k]; int y = j + dirs[k + 1]; if (x < m && y < n && grid[i][j] == grid[x][y]) { if (find(x * n + y) == find(i * n + j)) { return true; } p[find(x * n + y)] = find(i * n + j); } } } } return false; } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } } -
// OJ: https://leetcode.com/problems/detect-cycles-in-2d-grid/ // Time: O(MN) // Space: O(MN) class Solution { int seen[501][501] = {}, M, N, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }; bool dfs(vector<vector<char>> &G, int i, int j, int len = 1) { seen[i][j] = len; for (auto &[dx, dy] : dirs) { int x = i + dx, y = j + dy; if (x < 0 || x >= M || y < 0 || y >= N || G[x][y] != G[i][j] || (seen[x][y] && seen[i][j] - seen[x][y] < 3)) continue; if (seen[x][y] && seen[i][j] - seen[x][y] >= 3) return true; if (dfs(G, x, y, len + 1)) return true; } return false; } public: bool containsCycle(vector<vector<char>>& G) { M = G.size(), N = G[0].size(); for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { if (seen[i][j]) continue; if (dfs(G, i, j)) return true; } } return false; } }; -
class Solution: def containsCycle(self, grid: List[List[str]]) -> bool: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] m, n = len(grid), len(grid[0]) p = list(range(m * n)) for i in range(m): for j in range(n): for a, b in [[0, 1], [1, 0]]: x, y = i + a, j + b if x < m and y < n and grid[x][y] == grid[i][j]: if find(x * n + y) == find(i * n + j): return True p[find(x * n + y)] = find(i * n + j) return False -
func containsCycle(grid [][]byte) bool { m, n := len(grid), len(grid[0]) p := make([]int, m*n) for i := range p { p[i] = i } var find func(x int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } dirs := []int{1, 0, 1} for i := 0; i < m; i++ { for j := 0; j < n; j++ { for k := 0; k < 2; k++ { x, y := i+dirs[k], j+dirs[k+1] if x < m && y < n && grid[x][y] == grid[i][j] { if find(x*n+y) == find(i*n+j) { return true } p[find(x*n+y)] = find(i*n + j) } } } } return false } -
/** * @param {character[][]} grid * @return {boolean} */ var containsCycle = function (grid) { const m = grid.length; const n = grid[0].length; let p = Array.from({ length: m * n }, (_, i) => i); function find(x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } const dirs = [0, 1, 0]; for (let i = 0; i < m; ++i) { for (let j = 0; j < n; ++j) { for (let k = 0; k < 2; ++k) { const x = i + dirs[k]; const y = j + dirs[k + 1]; if (x < m && y < n && grid[x][y] == grid[i][j]) { if (find(x * n + y) == find(i * n + j)) { return true; } p[find(x * n + y)] = find(i * n + j); } } } } return false; };