Detect cycles in a 2D grid of integers using DFS

Given a 2D Grid consisting of integer values the task is to check whether there is a cycle in the grid or not . A valid cycle in the grid should follow the below conditions:

• All the values in the cycle should be same.
• Starting and ending point should be same.
• Cycle should contain at least 4 elements.

Note : Movement is allowed only the across the four adjacent directions in the matrix(left,right,up,down).

Examples :

Input : n = 4 , m = 4
1 2 3 4
4 2 4 4
2 1 4 4
3 3 1 9
Output : YES
Explanation :
the bold region in the matrix represents a cycle.



Input : n = 4 , m = 4
1 2 3 4
4 2 4 4
2 1 2 1
3 3 1 9
Output : NO
Explanation :
there is no cycle in the matrix .

Approach :

We can approah it the same way as finding the cycle in a graph i.e we can use DFS or BFS to find the cycle in the grid but we need to take care of the fact that the size of the cycle should be atleast 4 . To do that we need to keep the track of the parent of the current node so that to ensure that we do not count a cycle of size 2 and also we need to take care of the fact that all the elements in the cycle should be same .

C++14

// C++ Program to check
// cycle in 2D grid
#include <bits/stdc++.h>
using namespace std;

// rows and col in
// grid
int rows, col;
// Function to check
// whether the move is
// valid or not
bool isValidIndex(int i, int j)
{
    return (i >= 0 and j >= 0 and i < rows and j < col);
}
// Recursive Function to check
// whether cycle is
// possible
bool findCycle(int i, int j, vector<vector<int> >& grid,
               vector<vector<bool> >& vis, int value,
               pair<int, int> parent)
{
    // if already visited
    // then found the cycle

    if (vis[i][j] == true)
        return true;

    // mark as visited
    vis[i][j] = true;

    // to store the possibilty
    // for all the directions
    bool left, right, up, down;

    left = right = up = down = false;

    // to check the base
    // case for start of cycle
    pair<int, int> parent1 = { -1, -1 };

    // check for cycle through
    // down adjacent cell
    if (isValidIndex(i + 1, j)) {
        // check for same value
        // and should not be the same
        // as previous cell
        if (grid[i + 1][j] == value
            and (parent == parent1
                 or parent != make_pair(i + 1, j)))
            down = findCycle(i + 1, j, grid, vis, value,
                             { i, j });

        // if found no need
        // to check further
        if (down)
            return true;
    }
    // check for cycle
    // through up adjacent cell
    if (isValidIndex(i - 1, j)) {
        if (grid[i - 1][j] == value
            and (parent == parent1
                 or parent != make_pair(i - 1, j)))
            up = findCycle(i - 1, j, grid, vis, value,
                           { i, j });

        if (up)
            return true;
    }
    // check for cycle
    // through right adjacent cell

    if (isValidIndex(i, j + 1)) {
        if (grid[i][j + 1] == value
            and (parent == parent1
                 or parent != make_pair(i, j + 1)))
            right = findCycle(i, j + 1, grid, vis, value,
                              { i, j });

        if (right)
            return true;
    }
    // check for cycle
    // through left adjacent cell
    if (isValidIndex(i, j - 1)) {
        if (grid[i][j - 1] == value
            and (parent == parent1
                 or parent != make_pair(i, j - 1)))
            left = findCycle(i, j - 1, grid, vis, value,
                             { i, j });

        if (left)
            return true;
    }

    // if no cycle possible
    // in any direction
    return false;
}
bool checkCycle(vector<vector<int> >& grid)
{
    rows = grid.size();

    col = grid[0].size();

    // to store the status
    // of the cells
    vector<vector<bool> > vis(rows,
                              vector<bool>(col, false));

    // parent for source
    // of the cycle
    pair<int, int> parent = { -1, -1 };

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < col; j++) {
            // if the cell
            // is not visited check
            // for the cycle
            if (!vis[i][j]) {
                int value = grid[i][j];

                if (findCycle(i, j, grid, vis, value,
                              parent)) {
                    // cout << i << " " << j << " ";
                    return true;
                }
            }
        }
    }

    // no cycle found
    return false;
}
int main()
{
    // integer grid
    vector<vector<int> > grid = { { 1, 2, 3, 4 },
                                  { 4, 2, 4, 4 },
                                  { 2, 1, 4, 4 },
                                  { 3, 3, 1, 9 } };

    // boolean variable
    // to store the status
    bool foundCycle = checkCycle(grid);

    if (foundCycle)
        cout << "YES\n";
    else
        cout << "NO\n";

    return 0;
}

Time Complexity : O(N*M) , where N and M are rows and columns of the grid

Space Complexity : O(N*M)