# 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

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi