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 Sí .
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