Cycle find algorithm

Leetcode 1559. Detect Cycles in 2D Grid

Problem

Solutions

We can use a standard finding cycle algorithm to solve this problem. The basic idea is :

  1. define 3 states: visited, unvisited, explored.
  2. Explored means that the node is not finishing the visiting process.
  3. If during the DFS traversing process, we find a node with the states of Explored and that node is not the parent node of the current node, we find a cycle.
  4. The reason that we add the parent node checking is the bidirectional edge will be a cycle if we don’t have the check.
const int UNVISITED  = -1, VISITED = 1, EXPLORED = 0;
int di[4] = {0, 1, 0, -1};
int dj[4] = {1, 0, -1, 0};
class Solution {
public:
bool cycle_find(vector<vector<int>>& states, vector<vector<char>>& grid, map<pair<int, int>, pair<int, int>>& parents, int i, int j, char& ch) {
const int n = states.size(), m = states[0].size();
states[i][j] =EXPLORED;
for (int d = 0; d < 4; ++d) {
auto r = i + di[d], c = j + dj[d];
if (r >= 0 && r < n && c >= 0 && c < m && grid[r][c] == ch) {
if (states[r][c] == UNVISITED) {
parents[make_pair(r, c)] = make_pair(i, j);
if (cycle_find(states, grid, parents, r, c, ch)) {
return true;
}
}
else if (states[r][c] == EXPLORED) {
if (parents[make_pair(i, j)] != make_pair(r, c)) return true;
}
}
}
states[i][j] =VISITED;
return false;
}
bool containsCycle(vector<vector<char>>& grid) {
const int n = grid.size(), m = grid[0].size();
vector<vector<int>> states(n, vector<int>(m, UNVISITED));
map<pair<int, int>, pair<int, int>> parents;
for (int i = 0; i < n; ++i){
for (int j = 0; j < m; ++j) {
if (states[i][j] == UNVISITED) {
if (cycle_find(states, grid, parents, i, j, grid[i][j])) return true;
}
}
}
return false;
}
};
const int UNVISITED  = -1, VISITED = 1, EXPLORED = 0;
int di[4] = {0, 1, 0, -1};
int dj[4] = {1, 0, -1, 0};
class Solution {
public:
bool cycle_find(vector<int>& states, vector<vector<char>>& grid, map<int, int>& parents, int idx, const int n, const int m, char& ch) {
states[idx] =EXPLORED;
auto i = idx/m, j = idx%m;
for (int d = 0; d < 4; ++d) {
auto r = i + di[d], c = j + dj[d];
if (r >= 0 && r < n && c >= 0 && c < m && grid[r][c] == ch) {
auto new_idx = r*m + c;
if (states[new_idx] == UNVISITED) {
parents[new_idx] = idx;
if (cycle_find(states, grid, parents, new_idx, n, m, ch)) {
return true;
}
}
else if (states[new_idx] == EXPLORED) {
if (parents[idx] != new_idx) return true;
}
}
}
states[idx] =VISITED;
return false;
}
bool containsCycle(vector<vector<char>>& grid) {
const int n = grid.size(), m = grid[0].size();
vector<int> states(n*m, UNVISITED);
map<int, int> parents;
for (int i = 0; i < n; ++i){
for (int j = 0; j < m; ++j) {
auto idx = i*m + j;
if (states[idx] == UNVISITED) {
if (cycle_find(states, grid, parents, idx, n, m, grid[i][j])) return true;
}
}
}
return false;
}
};

Data Scientist/MLE/SWE @takemobi