Рубрики

Найти все вхождения данного слова в матрицу

По заданной двумерной сетке символов и слова найдите все вхождения данного слова в сетке. Слово может быть найдено во всех 8 направлениях в любой точке. Говорят, слово можно найти в направлении, если все символы совпадают в этом направлении (не в зигзагообразной форме).

Решение должно вывести все координаты, если найден цикл. т.е.

8 направлений: по горизонтали влево, по горизонтали вправо, вертикально вверх, вертикально вниз и 4 диагонали.

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) 

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.
Это в основном продолжение этого поста. Здесь с местами путь также напечатан.

Проблема может быть легко решена путем применения DFS () к каждому появлению первого символа слова в матрице. Ячейка в 2D-матрице может быть связана с 8 соседями. Таким образом, в отличие от стандартного DFS (), где мы рекурсивно вызываем все смежные вершины, здесь мы можем рекурсивно вызывать только 8 соседей.

// Программа для поиска всех вхождений слова в
// матрица
#include <bits/stdc++.h>

using namespace std;

  
#define ROW 3
#define COL 5

  
// проверяем, является ли данная ячейка (строка, столбец) допустимой
// ячейка или нет.

bool isvalid(int row, int col, int prevRow, int prevCol)

{

    // возвращаем true если номер строки и номер столбца

    // находится в диапазоне

    return (row >= 0) && (row < ROW) &&

           (col >= 0) && (col < COL) &&

           !(row== prevRow && col == prevCol);

}

  
// Эти массивы используются для получения строки и столбца
// числа 8 соседей данной ячейки

int rowNum[] = {-1, -1, -1, 0, 0, 1, 1, 1};

int colNum[] = {-1, 0, 1, -1, 1, -1, 0, 1};

  
// Вспомогательная функция для создания DFS для двумерного логического значения
// матрица Это только рассматривает 8 соседей как
// смежные вершины

void DFS(char mat[][COL], int row, int col,

         int prevRow, int prevCol, char* word,

         string path, int index, int n)

{

    // возвращаем, если текущий символ не совпадает с

    // следующий символ в слове

    if (index > n || mat[row][col] != word[index])

        return;

  

    // добавляем текущую позицию символа к пути

    path += string(1, word[index]) + "(" + to_string(row)

            + ", " + to_string(col) + ") ";

  

    // текущий символ совпадает с последним

    // в слове

    if (index == n)

    {

        cout << path << endl;

        return;

    }

  

    // повторить для всех подключенных соседей

    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);

}

  
// Основная функция для поиска всех вхождений
// слово в матрице

void findWords(char mat[][COL], char* word, int n)

{

    // пройти через все ячейки данной матрицы

    for (int i = 0; i < ROW; ++i)

        for (int j = 0; j < COL; ++j)

  

            // появление первого символа в матрице

            if (mat[i][j] == word[0])

  

                // проверяем и печатаем, если путь существует

                DFS(mat, i, j, -1, -1, word, "", 0, n);

}

  
// Программа драйвера для проверки вышеуказанной функции

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;

}

Выход :

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) 

Эта статья предоставлена Aditya Goel . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Найти все вхождения данного слова в матрицу

0.00 (0%) 0 votes