Detectar ciclo en una cuadrícula 2D

Dada una grilla 2D arr[][] con diferentes caracteres, la tarea es detectar si contiene un ciclo o no.

Una secuencia de caracteres o números enteros c 1 , c 2 , …. c M   se llama ciclo si y solo si cumple la siguiente condición:

  • M debería ser al menos 4.
  • Todos los caracteres pertenecen al mismo carácter o entero. Para todo 0 <= i <= M -1 : c i y c i + 1 son adyacentes.
  • Además, c M y c 1 también deben ser adyacentes, es decir, si comparten un borde común.

Ejemplos:

Entrada:  array[][] = {{‘A’, ‘A’, ‘A’, ‘A’},  

                         {‘A’, ‘B’, ‘C’, ‘A’},  

                        {‘AGREGA UN’}};
Salida: No
Explicación:
No hay ningún ciclo en la array anterior ya que no existe tal componente que cumpla con los requisitos de ser un ciclo.

Entrada:  array[N][M] = {{‘A’, ‘A’, ‘A’, ‘A’},                                

                              {‘A’, ‘B’, ‘C’, ‘A’},                                

                              {‘A’, ‘A’, ‘A’, ‘A’}};

Salida: Sí 
Explicación:
Las celdas mencionadas a continuación forman un ciclo porque se cumplen todos los requisitos.
{(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 3), (2, 0), (2, 1), ( 2, 2), (2, 3)}.

Enfoque: La idea es usar DFS Traversal en la grilla para detectar un ciclo en ella. A continuación se muestran los pasos: 

  • Elija cada celda de la array dada ((0, 0) a (N – 1, M – 1)) porque no hay una posición definida del ciclo.
  • Si existe un ciclo, entonces todas las celdas del ciclo deben tener el mismo valor, y deben estar conectadas y también comprobar que el último y el primer elemento deben formar un bucle (deben tener diferentes padres).
  • Tome una variable booleana que almacenará el resultado de la función isCycle() que será un 1 o un 0 respectivamente, indicando si hay un ciclo o no. Si la función devuelve 1, cambie la variable ans a verdadero y rompa el ciclo; de lo contrario, continúe.
  • Si la respuesta permanece sin marcar hasta la última, imprima  No ; de lo contrario, imprima .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Define size of grid
#define N 3
#define M 4
 
// To store direction of all the four
// adjacent cells
const int directionInX[4] = { -1, 0, 1, 0 };
const int directionInY[4] = { 0, 1, 0, -1 };
 
// Boolean function for checking
// if a cell is valid or not
bool isValid(int x, int y)
{
    if (x < N && x >= 0
        && y < M && y >= 0)
        return 1;
 
    return 0;
}
 
// Boolean function which will check
// whether the given array consist
// of a cycle or not
bool isCycle(int x, int y, char arr[N][M],
            bool visited[N][M],
            int parentX, int parentY)
{
    // Mark the current vertex true
    visited[x][y] = true;
 
    // Loop for generate all possibilities
    // of adjacent cells and checking them
    for (int k = 0; k < 4; k++) {
 
        int newX = x + directionInX[k];
        int newY = y + directionInY[k];
 
        if (isValid(newX, newY) == 1
            && arr[newX][newY] == arr[x][y]
            && !(parentX == newX
                and parentY == newY)) {
 
            // Check if there exist
            // cycle then return true
            if (visited[newX][newY] == 1) {
 
                // Return 1 because the
                // cycle exists
                return true;
            }
 
            // Check if not found,
            // keep checking recursively
            else {
                bool check
                    = isCycle(newX, newY, arr,
                            visited, x, y);
 
                // Now, if check comes out
                // to be true then return 1
                // indicating there exist cycle
                if (check == 1)
                    return true;
            }
        }
    }
 
    // If there was no cycle,
    // taking x and y as source
    // then return false
    return false;
}
 
// Function to detect Cycle in a grid
void detectCycle(char arr[N][M])
{
 
    // To store the visited cell
    bool visited[N][M];
 
    // Initially marking all
    // the cells as unvisited
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            visited[i][j] = false;
 
    // Boolean variable for
    // storing the result
    bool cycle = 0;
 
    // As there is no fix position
    // of Cycle we will have to
    // check for every arr[i][j]
    for (int i = 0; i < N; i++) {
 
        // If cycle is present and
        // we have already detected
        // it, then break this loop
        if (cycle == true)
            break;
 
        for (int j = 0; j < M; j++) {
 
            // Taking (-1, -1) as
            // source node's parent
            if (visited[i][j] == 0) {
                cycle = isCycle(i, j, arr,
                                visited, -1, -1);
            }
 
            // If we have encountered a
            // cycle then break this loop
            if (cycle == true)
                break;
        }
    }
 
    // Cycle was encountered
    if (cycle == true) {
        cout << "Yes";
    }
 
    // Cycle was not encountered
    else {
        cout << "No";
    }
}
 
// Driver code
int main()
{
    // Given grid arr[][]
    char arr[N][M] = { { 'A', 'A', 'A', 'A' },
                    { 'A', 'B', 'C', 'A' },
                    { 'A', 'D', 'D', 'A' } };
 
    // Function Call
    detectCycle(arr);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Define size of grid
static final int N = 3;
static final int M = 4;
 
// To store direction of all the four
// adjacent cells
static int directionInX[] = new int[]{ -1, 0, 1, 0 };
static int directionInY[] = new int[]{ 0, 1, 0, -1 };
 
// Boolean function for checking
// if a cell is valid or not
static boolean isValid(int x, int y)
{
    if (x < N && x >= 0 &&
        y < M && y >= 0)
        return true;
    else
        return false;
}
 
 
// Boolean function which will check
// whether the given array consist
// of a cycle or not
static boolean isCycle(int x, int y, char arr[][],
                    boolean visited[][],
                    int parentX, int parentY)
{
     
    // Mark the current vertex true
    visited[x][y] = true;
 
    // Loop for generate all possibilities
    // of adjacent cells and checking them
    for(int k = 0; k < 4; k++)
    {
        int newX = x + directionInX[k];
        int newY = y + directionInY[k];
 
        if (isValid(newX, newY) == true &&
            arr[newX][newY] == arr[x][y] &&
            !(parentX == newX && parentY == newY))
        {
             
            // Check if there exist
            // cycle then return true
            if (visited[newX][newY] == true)
            {
                 
                // Return 1 because the
                // cycle exists
                return true;
            }
 
            // Check if not found,
            // keep checking recursively
            else
            {
                boolean check = isCycle(newX, newY,
                                        arr, visited,
                                        x, y);
 
                // Now, if check comes out
                // to be true then return 1
                // indicating there exist cycle
                if (check == true)
                    return true;
            }
        }
    }
     
    // If there was no cycle,
    // taking x and y as source
    // then return false
    return false;
}
 
// Function to detect Cycle in a grid
static void detectCycle(char arr[][])
{
     
    // To store the visited cell
    boolean [][]visited = new boolean[N][M];
 
    // Initially marking all
    // the cells as unvisited
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            visited[i][j] = false;
 
    // Boolean variable for
    // storing the result
    boolean cycle = false;
 
    // As there is no fix position
    // of Cycle we will have to
    // check for every arr[i][j]
    for(int i = 0; i < N; i++)
    {
         
        // If cycle is present and
        // we have already detected
        // it, then break this loop
        if (cycle == true)
            break;
 
        for(int j = 0; j < M; j++)
        {
             
            // Taking (-1, -1) as
            // source node's parent
            if (visited[i][j] == false)
            {
                cycle = isCycle(i, j, arr,
                                visited, -1, -1);
            }
             
            // If we have encountered a
            // cycle then break this loop
            if (cycle == true)
                break;
        }
    }
 
    // Cycle was encountered
    if (cycle == true)
    {
        System.out.print("Yes");
    }
     
    // Cycle was not encountered
    else
    {
        System.out.print("No");
    }
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given grid arr[][]
    char arr[][] = { { 'A', 'A', 'A', 'A' },
                    { 'A', 'B', 'C', 'A' },
                    { 'A', 'D', 'D', 'A' } };
 
    // Function call
    detectCycle(arr);
}
}
 
// This code is contributed by amal kumar choubey

Python3

# Python3 program for the above approach
 
# Store direction of all the four
# adjacent cells. We'll move along
# the grid using pairs of values
directionInX = [ -1, 0, 1, 0 ]
directionInY = [ 0, 1, 0, -1 ]
 
# Function for checking
# if a cell is valid or not
def isValid(x, y, N, M):
     
    if (x < N and x >= 0 and
        y < M and y >= 0):
        return True
         
    return False
 
# Function which will check whether
# the given array consist of a cycle or not
def isCycle(x, y, arr, visited, parentX, parentY):
     
    # Mark the current vertex as visited
    visited[x][y] = True
     
    N, M = 3, 4
     
    # Loop for generate all possibilities
    # of adjacent cells and checking them
    for k in range(4):
        newX = x + directionInX[k]
        newY = y + directionInY[k]
         
        if (isValid(newX, newY, N, M) and
            arr[newX][newY] == arr[x][y] and
               not (parentX == newX and
                    parentY == newY)):
                            
            # Check if there exist
            # cycle then return true
            if visited[newX][newY]:
                 
                # Return True as the
                # cycle exists
                return True
                 
            # If the cycle is not found
            # then keep checking recursively
            else:
                check = isCycle(newX, newY, arr,
                                visited, x, y)
                if check:
                    return True
                     
    # If there was no cycle, taking
    # x and y as source then return false
    return False
 
# Function to detect Cycle in a grid
def detectCycle(arr):
     
    N, M = 3, 4
     
    # Initially all the cells are unvisited
    visited = [[False] * M for _ in range(N)]
 
    # Variable to store the result
    cycle = False
 
    # As there is no fixed position
    # of the cycle we have to loop
    # through all the elements
    for i in range(N):
         
        # If cycle is present and
        # we have already detected
        # it, then break this loop
        if cycle == True:
            break
 
        for j in range(M):
             
            # Taking (-1, -1) as source
            # node's parent
            if visited[i][j] == False:
                cycle = isCycle(i, j, arr,
                                visited, -1, -1)
             
            # If we have encountered a
            # cycle then break this loop
            if cycle == True:
                break
     
    # Cycle was encountered
    if cycle == True:
        print("Yes")
         
    # Cycle was not encountered
    else:
        print("No")
 
# Driver code
arr = [ [ 'A', 'A', 'A', 'A' ],
        [ 'A', 'B', 'C', 'A' ],
        [ 'A', 'D', 'D', 'A' ] ]
 
# Function call
detectCycle(arr)
 
# This code is contributed by soum1071

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Define size of grid
static readonly int N = 3;
static readonly int M = 4;
 
// To store direction of all the four
// adjacent cells
static int []directionInX = new int[]{ -1, 0, 1, 0 };
static int []directionInY = new int[]{ 0, 1, 0, -1 };
 
// Boolean function for checking
// if a cell is valid or not
static bool isValid(int x, int y)
{
    if (x < N && x >= 0 &&
        y < M && y >= 0)
        return true;
    else
        return false;
}
 
// Boolean function which will check
// whether the given array consist
// of a cycle or not
static bool isCycle(int x, int y, char [,]arr,
                    bool [,]visited,
                    int parentX, int parentY)
{
     
    // Mark the current vertex true
    visited[x, y] = true;
 
    // Loop for generate all possibilities
    // of adjacent cells and checking them
    for(int k = 0; k < 4; k++)
    {
        int newX = x + directionInX[k];
        int newY = y + directionInY[k];
 
        if (isValid(newX, newY) == true &&
            arr[newX, newY] == arr[x, y] &&
            !(parentX == newX && parentY == newY))
        {
             
            // Check if there exist
            // cycle then return true
            if (visited[newX, newY] == true)
            {
                 
                // Return 1 because the
                // cycle exists
                return true;
            }
 
            // Check if not found,
            // keep checking recursively
            else
            {
                bool check = isCycle(newX, newY,
                                    arr, visited,
                                    x, y);
 
                // Now, if check comes out
                // to be true then return 1
                // indicating there exist cycle
                if (check == true)
                    return true;
            }
        }
    }
     
    // If there was no cycle,
    // taking x and y as source
    // then return false
    return false;
}
 
// Function to detect Cycle in a grid
static void detectCycle(char [,]arr)
{
     
    // To store the visited cell
    bool [,]visited = new bool[N, M];
 
    // Initially marking all
    // the cells as unvisited
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            visited[i, j] = false;
 
    // Boolean variable for
    // storing the result
    bool cycle = false;
 
    // As there is no fix position
    // of Cycle we will have to
    // check for every arr[i,j]
    for(int i = 0; i < N; i++)
    {
         
        // If cycle is present and
        // we have already detected
        // it, then break this loop
        if (cycle == true)
            break;
 
        for(int j = 0; j < M; j++)
        {
             
            // Taking (-1, -1) as
            // source node's parent
            if (visited[i, j] == false)
            {
                cycle = isCycle(i, j, arr,
                                visited, -1, -1);
            }
             
            // If we have encountered a
            // cycle then break this loop
            if (cycle == true)
                break;
        }
    }
 
    // Cycle was encountered
    if (cycle == true)
    {
        Console.Write("Yes");
    }
     
    // Cycle was not encountered
    else
    {
        Console.Write("No");
    }
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Given grid [,]arr
    char [,]arr = { { 'A', 'A', 'A', 'A' },
                    { 'A', 'B', 'C', 'A' },
                    { 'A', 'D', 'D', 'A' } };
 
    // Function call
    detectCycle(arr);
}
}
 
// This code is contributed by amal kumar choubey

Javascript

<script>
    // Javascript program for the above approach
     
    // Define size of grid
    let N = 3;
    let M = 4;
 
    // To store direction of all the four
    // adjacent cells
    let directionInX = [ -1, 0, 1, 0 ];
    let directionInY = [ 0, 1, 0, -1 ];
 
    // Boolean function for checking
    // if a cell is valid or not
    function isValid(x, y)
    {
        if (x < N && x >= 0 &&
            y < M && y >= 0)
            return true;
        else
            return false;
    }
 
 
    // Boolean function which will check
    // whether the given array consist
    // of a cycle or not
    function isCycle(x, y, arr, visited, parentX, parentY)
    {
 
        // Mark the current vertex true
        visited[x][y] = true;
 
        // Loop for generate all possibilities
        // of adjacent cells and checking them
        for(let k = 0; k < 4; k++)
        {
            let newX = x + directionInX[k];
            let newY = y + directionInY[k];
 
            if (isValid(newX, newY) == true &&
                arr[newX][newY] == arr[x][y] &&
                !(parentX == newX && parentY == newY))
            {
 
                // Check if there exist
                // cycle then return true
                if (visited[newX][newY] == true)
                {
 
                    // Return 1 because the
                    // cycle exists
                    return true;
                }
 
                // Check if not found,
                // keep checking recursively
                else
                {
                    let check = isCycle(newX, newY,
                                            arr, visited,
                                            x, y);
 
                    // Now, if check comes out
                    // to be true then return 1
                    // indicating there exist cycle
                    if (check == true)
                        return true;
                }
            }
        }
 
        // If there was no cycle,
        // taking x and y as source
        // then return false
        return false;
    }
 
    // Function to detect Cycle in a grid
    function detectCycle(arr)
    {
 
        // To store the visited cell
        let visited = new Array(N);
 
        // Initially marking all
        // the cells as unvisited
        for(let i = 0; i < N; i++)
        {
            visited[i] = new Array(M);
            for(let j = 0; j < M; j++)
            {
                visited[i][j] = false;
            }
        }
 
        // Boolean variable for
        // storing the result
        let cycle = false;
 
        // As there is no fix position
        // of Cycle we will have to
        // check for every arr[i][j]
        for(let i = 0; i < N; i++)
        {
 
            // If cycle is present and
            // we have already detected
            // it, then break this loop
            if (cycle == true)
                break;
 
            for(let j = 0; j < M; j++)
            {
 
                // Taking (-1, -1) as
                // source node's parent
                if (visited[i][j] == false)
                {
                    cycle = isCycle(i, j, arr,
                                    visited, -1, -1);
                }
 
                // If we have encountered a
                // cycle then break this loop
                if (cycle == true)
                    break;
            }
        }
 
        // Cycle was encountered
        if (cycle == true)
        {
            document.write("Yes");
        }
 
        // Cycle was not encountered
        else
        {
            document.write("No");
        }
    }
     
    // Given grid arr[][]
    let arr = [ [ 'A', 'A', 'A', 'A' ],
                 [ 'A', 'B', 'C', 'A' ],
                 [ 'A', 'D', 'D', 'A' ] ];
  
    // Function call
    detectCycle(arr);
 
// This code is contributed by divyeshrabadiy07.
</script>
Producción: 

No

 

Complejidad de Tiempo : O(N * M)
Espacio Auxiliar: O(N * M)

Publicación traducida automáticamente

Artículo escrito por reapedjuggler y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *