Cycle find algorithm

Leetcode 1559. Detect Cycles in 2D Grid

Problem

1559. Detect Cycles in 2D Grid

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.

Straightforward implementation (runtime 1000 ms)

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;
    }
};

A little bit faster version (800 ms)

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;
    }
};