Dada una cuadrícula 2D de caracteres y una palabra, encuentre todas las apariciones de la palabra dada en la cuadrícula. Una palabra puede coincidir en las 8 direcciones en cualquier punto. Se dice que la palabra se encuentra en una dirección si todos los caracteres coinciden en esta dirección (no en forma de zig-zag).
La solución debe imprimir todas las coordenadas si se encuentra un ciclo. es decir,
las 8 direcciones son, horizontalmente a la izquierda, horizontalmente a la derecha, verticalmente hacia arriba, verticalmente hacia abajo y 4 diagonales.
Input:
mat[ROW][COL]= { {'B', 'N', 'E', 'Y', 'S'},
{'H', 'E', 'D', 'E', 'S'},
{'S', 'G', 'N', 'D', 'E'}
};
Word = “DES”
Output:
D(1, 2) E(1, 1) S(2, 0)
D(1, 2) E(1, 3) S(0, 4)
D(1, 2) E(1, 3) S(1, 4)
D(2, 3) E(1, 3) S(0, 4)
D(2, 3) E(1, 3) S(1, 4)
D(2, 3) E(2, 4) S(1, 4)
Input:
char mat[ROW][COL] = { {'B', 'N', 'E', 'Y', 'S'},
{'H', 'E', 'D', 'E', 'S'},
{'S', 'G', 'N', 'D', 'E'}};
char word[] ="BNEGSHBN";
Output:
B(0, 0) N(0, 1) E(1, 1) G(2, 1) S(2, 0) H(1, 0)
B(0, 0) N(0, 1)
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Esto es principalmente una extensión de este post. Aquí con la ruta de ubicación también se imprime.
El problema se puede resolver fácilmente aplicando DFS() en cada aparición del primer carácter de la palabra en la array. Una celda en array 2D se puede conectar a 8 vecinos. Entonces, a diferencia del DFS() estándar, donde recursivamente llamamos a todos los vértices adyacentes, aquí podemos llamar recursivamente solo a 8 vecinos.
CPP
// Program to find all occurrences of the word in
// a matrix
#include <bits/stdc++.h>
using namespace std;
#define ROW 3
#define COL 5
// check whether given cell (row, col) is a valid
// cell or not.
bool isvalid(int row, int col, int prevRow, int prevCol)
{
// return true if row number and column number
// is in range
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL) &&
!(row== prevRow && col == prevCol);
}
// These arrays are used to get row and column
// numbers of 8 neighboursof a given cell
int rowNum[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int colNum[] = {-1, 0, 1, -1, 1, -1, 0, 1};
// A utility function to do DFS for a 2D boolean
// matrix. It only considers the 8 neighbours as
// adjacent vertices
void DFS(char mat[][COL], int row, int col,
int prevRow, int prevCol, char* word,
string path, int index, int n)
{
// return if current character doesn't match with
// the next character in the word
if (index > n || mat[row][col] != word[index])
return;
//append current character position to path
path += string(1, word[index]) + "(" + to_string(row)
+ ", " + to_string(col) + ") ";
// current character matches with the last character
// in the word
if (index == n)
{
cout << path << endl;
return;
}
// Recur for all connected neighbours
for (int k = 0; k < 8; ++k)
if (isvalid(row + rowNum[k], col + colNum[k],
prevRow, prevCol))
DFS(mat, row + rowNum[k], col + colNum[k],
row, col, word, path, index+1, n);
}
// The main function to find all occurrences of the
// word in a matrix
void findWords(char mat[][COL], char* word, int n)
{
// traverse through the all cells of given matrix
for (int i = 0; i < ROW; ++i)
for (int j = 0; j < COL; ++j)
// occurrence of first character in matrix
if (mat[i][j] == word[0])
// check and print if path exists
DFS(mat, i, j, -1, -1, word, "", 0, n);
}
// Driver program to test above function
int main()
{
char mat[ROW][COL]= { {'B', 'N', 'E', 'Y', 'S'},
{'H', 'E', 'D', 'E', 'S'},
{'S', 'G', 'N', 'D', 'E'}
};
char word[] ="DES";
findWords(mat, word, strlen(word) - 1);
return 0;
}
Java
// Java Program to find all occurrences of the word in
// a matrix
import java.util.*;
class GFG
{
static final int ROW = 3;
static final int COL = 5;
// check whether given cell (row, col) is a valid
// cell or not.
static boolean isvalid(int row, int col, int prevRow, int prevCol)
{
// return true if row number and column number
// is in range
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL) &&
!(row == prevRow && col == prevCol);
}
// These arrays are used to get row and column
// numbers of 8 neighboursof a given cell
static int rowNum[] = {-1, -1, -1, 0, 0, 1, 1, 1};
static int colNum[] = {-1, 0, 1, -1, 1, -1, 0, 1};
// A utility function to do DFS for a 2D boolean
// matrix. It only considers the 8 neighbours as
// adjacent vertices
static void DFS(char mat[][], int row, int col,
int prevRow, int prevCol, char[] word,
String path, int index, int n)
{
// return if current character doesn't match with
// the next character in the word
if (index > n || mat[row][col] != word[index])
return;
// append current character position to path
path += (word[index]) + "(" + String.valueOf(row)
+ ", " + String.valueOf(col) + ") ";
// current character matches with the last character
// in the word
if (index == n)
{
System.out.print(path +"\n");
return;
}
// Recur for all connected neighbours
for (int k = 0; k < 8; ++k)
if (isvalid(row + rowNum[k], col + colNum[k],
prevRow, prevCol))
DFS(mat, row + rowNum[k], col + colNum[k],
row, col, word, path, index + 1, n);
}
// The main function to find all occurrences of the
// word in a matrix
static void findWords(char mat[][], char []word, int n)
{
// traverse through the all cells of given matrix
for (int i = 0; i < ROW; ++i)
for (int j = 0; j < COL; ++j)
// occurrence of first character in matrix
if (mat[i][j] == word[0])
// check and print if path exists
DFS(mat, i, j, -1, -1, word, "", 0, n);
}
// Driver code
public static void main(String[] args)
{
char mat[][]= { {'B', 'N', 'E', 'Y', 'S'},
{'H', 'E', 'D', 'E', 'S'},
{'S', 'G', 'N', 'D', 'E'}};
char []word ="DES".toCharArray();
findWords(mat, word, word.length - 1);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 Program to find all occurrences of the word in
# a matrix
ROW = 3
COL = 5
# check whether given cell (row, col) is a valid
# cell or not.
def isvalid(row, col, prevRow, prevCol):
# return true if row number and column number
# is in range
return (row >= 0) and (row < ROW) and (col >= 0) and \
(col < COL) and not (row== prevRow and col == prevCol)
# These arrays are used to get row and column
# numbers of 8 neighboursof a given cell
rowNum = [-1, -1, -1, 0, 0, 1, 1, 1]
colNum = [-1, 0, 1, -1, 1, -1, 0, 1]
# A utility function to do DFS for a 2D boolean
# matrix. It only considers the 8 neighbours as
# adjacent vertices
def DFS(mat, row, col,prevRow, prevCol, word,path, index, n):
# return if current character doesn't match with
# the next character in the word
if (index > n or mat[row][col] != word[index]):
return
# append current character position to path
path += word[index] + "(" + str(row)+ ", " + str(col) + ") "
# current character matches with the last character\
# in the word
if (index == n):
print(path)
return
# Recur for all connected neighbours
for k in range(8):
if (isvalid(row + rowNum[k], col + colNum[k],prevRow, prevCol)):
DFS(mat, row + rowNum[k], col + colNum[k],row, col, word, path, index + 1, n)
# The main function to find all occurrences of the
# word in a matrix
def findWords(mat,word, n):
# traverse through the all cells of given matrix
for i in range(ROW):
for j in range(COL):
# occurrence of first character in matrix
if (mat[i][j] == word[0]):
# check and print if path exists
DFS(mat, i, j, -1, -1, word, "", 0, n)
# Driver code
mat = [['B', 'N', 'E', 'Y', 'S'],
['H', 'E', 'D', 'E', 'S'],
['S', 'G', 'N', 'D', 'E']]
word = list("DES")
findWords(mat, word, len(word) - 1)
# This code is contributed by SHUBHAMSINGH10
C#
// C# Program to find all occurrences of the word in
// a matrix
using System;
class GFG
{
static readonly int ROW = 3;
static readonly int COL = 5;
// check whether given cell (row, col) is a valid
// cell or not.
static bool isvalid(int row, int col, int prevRow, int prevCol)
{
// return true if row number and column number
// is in range
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL) &&
!(row == prevRow && col == prevCol);
}
// These arrays are used to get row and column
// numbers of 8 neighboursof a given cell
static int []rowNum = {-1, -1, -1, 0, 0, 1, 1, 1};
static int []colNum = {-1, 0, 1, -1, 1, -1, 0, 1};
// A utility function to do DFS for a 2D bool
// matrix. It only considers the 8 neighbours as
// adjacent vertices
static void DFS(char [,]mat, int row, int col,
int prevRow, int prevCol, char[] word,
String path, int index, int n)
{
// return if current character doesn't match with
// the next character in the word
if (index > n || mat[row,col] != word[index])
return;
// append current character position to path
path += (word[index]) + "(" + String.Join("",row)
+ ", " + String.Join("",col) + ") ";
// current character matches with the last character
// in the word
if (index == n)
{
Console.Write(path +"\n");
return;
}
// Recur for all connected neighbours
for (int k = 0; k < 8; ++k)
if (isvalid(row + rowNum[k], col + colNum[k],
prevRow, prevCol))
DFS(mat, row + rowNum[k], col + colNum[k],
row, col, word, path, index + 1, n);
}
// The main function to find all occurrences of the
// word in a matrix
static void findWords(char [,]mat, char []word, int n)
{
// traverse through the all cells of given matrix
for (int i = 0; i < ROW; ++i)
for (int j = 0; j < COL; ++j)
// occurrence of first character in matrix
if (mat[i,j] == word[0])
// check and print if path exists
DFS(mat, i, j, -1, -1, word, "", 0, n);
}
// Driver code
public static void Main(String[] args)
{
char [,]mat= { {'B', 'N', 'E', 'Y', 'S'},
{'H', 'E', 'D', 'E', 'S'},
{'S', 'G', 'N', 'D', 'E'}};
char []word ="DES".ToCharArray();
findWords(mat, word, word.Length - 1);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript Program to find all occurrences of the word in
// a matrix
let ROW = 3;
let COL = 5;
// check whether given cell (row, col) is a valid
// cell or not.
function isvalid(row, col, prevRow, prevCol)
{
// return true if row number and column number
// is in range
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL) &&
!(row == prevRow && col == prevCol);
}
// These arrays are used to get row and column
// numbers of 8 neighboursof a given cell
let rowNum=[-1, -1, -1, 0, 0, 1, 1, 1];
let colNum=[-1, 0, 1, -1, 1, -1, 0, 1];
// A utility function to do DFS for a 2D boolean
// matrix. It only considers the 8 neighbours as
// adjacent vertices
function DFS(mat, row, col, prevRow, prevCol, word, path, index, n)
{
// return if current character doesn't match with
// the next character in the word
if (index > n || mat[row][col] != word[index])
return;
// append current character position to path
path += (word[index]) + "(" + (row).toString()
+ ", " + (col).toString() + ") ";
// current character matches with the last character
// in the word
if (index == n)
{
document.write(path +"<br>");
return;
}
// Recur for all connected neighbours
for (let k = 0; k < 8; ++k)
if (isvalid(row + rowNum[k], col + colNum[k],
prevRow, prevCol))
DFS(mat, row + rowNum[k], col + colNum[k],
row, col, word, path, index + 1, n);
}
// The main function to find all occurrences of the
// word in a matrix
function findWords(mat, word, n)
{
// traverse through the all cells of given matrix
for (let i = 0; i < ROW; ++i)
for (let j = 0; j < COL; ++j)
// occurrence of first character in matrix
if (mat[i][j] == word[0])
// check and print if path exists
DFS(mat, i, j, -1, -1, word, "", 0, n);
}
// Driver code
let mat = [['B', 'N', 'E', 'Y', 'S'],
['H', 'E', 'D', 'E', 'S'],
['S', 'G', 'N', 'D', 'E']];
let word = "DES".split("");
findWords(mat, word, word.length - 1);
// This code is contributed by rag2127
</script>
Producción :
D(1, 2) E(1, 1) S(2, 0) D(1, 2) E(1, 3) S(0, 4) D(1, 2) E(1, 3) S(1, 4) D(2, 3) E(1, 3) S(0, 4) D(2, 3) E(1, 3) S(1, 4) D(2, 3) E(2, 4) S(1, 4)
Complejidad de tiempo: O (fila x columna)
Espacio auxiliar: O (fila x columna)
Este artículo es una contribución de Aarti_Rathi y Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA