Рубрики

Boggle (Найти все возможные слова в доске символов) | Комплект 1

Имеется словарь, метод для поиска в словаре и доска M x N, где в каждой ячейке есть один символ. Найдите все возможные слова, которые могут быть образованы последовательностью соседних символов. Обратите внимание, что мы можем перейти к любому из 8 соседних символов, но слово не должно иметь несколько экземпляров одной и той же ячейки.

Пример:

Input: dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"};
       boggle[][]   = {{'G', 'I', 'Z'},
                       {'U', 'E', 'K'},
                       {'Q', 'S', 'E'}};
      isWord(str): returns true if str is present in dictionary
                   else false.

Output:  Following words of dictionary are present
         GEEKS
         QUIZ

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Идея состоит в том, чтобы рассматривать каждый символ как начальный символ и находить все слова, начинающиеся с него. Все слова, начинающиеся с символа, могут быть найдены с помощью Depth First Traversal . Мы выполняем глубинный обход, начиная с каждой ячейки. Мы отслеживаем посещенные ячейки, чтобы убедиться, что ячейка рассматривается только один раз в слове.

C ++

// C ++ программа для игры Boggle
#include <cstring>
#include <iostream>

using namespace std;

  
#define M 3
#define N 3

  
// Пусть данный словарь будет следующим

string dictionary[] = { "GEEKS", "FOR", "QUIZ", "GO" };

int n = sizeof(dictionary) / sizeof(dictionary[0]);

  
// Данная функция проверяет, присутствует ли данная строка в
// Словарь. Реализация наивна для простоты. В качестве
// по словарю вопроса дается нам.

bool isWord(string& str)

{

    // Линейный поиск всех слов

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

        if (str.compare(dictionary[i]) == 0)

            return true;

    return false;

}

  
// Рекурсивная функция для печати всех слов, присутствующих на boggle

void findWordsUtil(char boggle[M][N], bool visited[M][N], int i,

                   int j, string& str)

{

    // Пометить текущую ячейку как посещенную и добавить текущий символ

    // на стр

    visited[i][j] = true;

    str = str + boggle[i][j];

  

    // Если в словаре присутствует str, то вывести его

    if (isWord(str))

        cout << str << endl;

  

    // Пересекаем 8 соседних ячеек boggle [i] [j]

    for (int row = i - 1; row <= i + 1 && row < M; row++)

        for (int col = j - 1; col <= j + 1 && col < N; col++)

            if (row >= 0 && col >= 0 && !visited[row][col])

                findWordsUtil(boggle, visited, row, col, str);

  

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

    // текущей ячейки как ложной

    str.erase(str.length() - 1);

    visited[i][j] = false;

}

  
// Печатает все слова, присутствующие в словаре.

void findWords(char boggle[M][N])

{

    // Пометить все символы как не посещенные

    bool visited[M][N] = { { false } };

  

    // Инициализируем текущую строку

    string str = "";

  

    // Рассмотрим каждый символ и ищем все слова

    // начинаем с этого символа

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

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

            findWordsUtil(boggle, visited, i, j, str);

}

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

int main()

{

    char boggle[M][N] = { { 'G', 'I', 'Z' },

                          { 'U', 'E', 'K' },

                          { 'Q', 'S', 'E' } };

  

    cout << "Following words of dictionary are present\n";

    findWords(boggle);

    return 0;

}

Джава

// Java-программа для игры Boggle

class GFG {

    // Пусть данный словарь будет следующим

    static final String dictionary[] = { "GEEKS", "FOR", "QUIZ", "GUQ", "EE" };

    static final int n = dictionary.length;

    static final int M = 3, N = 3;

  

    // Данная функция проверяет, присутствует ли данная строка в

    // Словарь. Реализация наивна для простоты. В качестве

    // по словарю вопроса дается нам.

    static boolean isWord(String str)

    {

        // Линейный поиск всех слов

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

            if (str.equals(dictionary[i]))

                return true;

        return false;

    }

  

    // Рекурсивная функция для печати всех слов, присутствующих на boggle

    static void findWordsUtil(char boggle[][], boolean visited[][], int i,

                              int j, String str)

    {

        // Пометить текущую ячейку как посещенную и добавить текущий символ

        // на стр

        visited[i][j] = true;

        str = str + boggle[i][j];

  

        // Если в словаре присутствует str, то вывести его

        if (isWord(str))

            System.out.println(str);

  

        // Пересекаем 8 соседних ячеек boggle [i] [j]

        for (int row = i - 1; row <= i + 1 && row < M; row++)

            for (int col = j - 1; col <= j + 1 && col < N; col++)

                if (row >= 0 && col >= 0 && !visited[row][col])

                    findWordsUtil(boggle, visited, row, col, str);

  

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

        // текущей ячейки как ложной

        str = "" + str.charAt(str.length() - 1);

        visited[i][j] = false;

    }

  

    // Печатает все слова, присутствующие в словаре.

    static void findWords(char boggle[][])

    {

        // Пометить все символы как не посещенные

        boolean visited[][] = new boolean[M][N];

  

        // Инициализируем текущую строку

        String str = "";

  

        // Рассмотрим каждый символ и ищем все слова

        // начинаем с этого символа

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

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

                findWordsUtil(boggle, visited, i, j, str);

    }

  

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

    public static void main(String args[])

    {

        char boggle[][] = { { 'G', 'I', 'Z' },

                            { 'U', 'E', 'K' },

                            { 'Q', 'S', 'E' } };

  

        System.out.println("Following words of dictionary are present");

        findWords(boggle);

    }

}

C #

// C # программа для игры Boggle

using System;

using System.Collections.Generic;

  

class GFG 

{

    // Пусть данный словарь будет следующим

    static readonly String []dictionary = { "GEEKS", "FOR"

                                            "QUIZ", "GUQ", "EE" };

    static readonly int n = dictionary.Length;

    static readonly int M = 3, N = 3;

  

    // Данная функция проверяет, является ли данная строка

    // присутствует в словаре. Реализация

    // наивно для простоты. По вопросу

    // словарь дан нам.

    static bool isWord(String str)

    {

        // Линейный поиск всех слов

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

            if (str.Equals(dictionary[i]))

                return true;

        return false;

    }

  

    // Рекурсивная функция для печати всех слов, присутствующих на boggle

    static void findWordsUtil(char [,]boggle, bool [,]visited, 

                              int i, int j, String str)

    {

        // Пометить текущую ячейку как посещенную и

        // добавляем текущий символ в str

        visited[i, j] = true;

        str = str + boggle[i, j];

  

        // Если str присутствует в словаре,

        // затем распечатать

        if (isWord(str))

            Console.WriteLine(str);

  

        // Пересекаем 8 соседних ячеек boggle [i, j]

        for (int row = i - 1; row <= i + 1 && row < M; row++)

            for (int col = j - 1; col <= j + 1 && col < N; col++)

                if (row >= 0 && col >= 0 && !visited[row, col])

                    findWordsUtil(boggle, visited, row, col, str);

  

        // Удалить текущий символ из строки и

        // помечаем посещение текущей ячейки как ложное

        str = "" + str[str.Length - 1];

        visited[i, j] = false;

    }

  

    // Печатает все слова, присутствующие в словаре.

    static void findWords(char [,]boggle)

    {

        // Пометить все символы как не посещенные

        bool [,]visited = new bool[M, N];

  

        // Инициализируем текущую строку

        String str = "";

  

        // Рассмотрим каждый символ и ищем все слова

        // начинаем с этого символа

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

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

                findWordsUtil(boggle, visited, i, j, str);

    }

  

    // Код драйвера

    public static void Main(String []args)

    {

        char [,]boggle = { { 'G', 'I', 'Z' },

                           { 'U', 'E', 'K' },

                           { 'Q', 'S', 'E' } };

  

        Console.WriteLine("Following words of " +  

                          "dictionary are present");

        findWords(boggle);

    }

}

  
// Этот код предоставлен PrinciRaj1992

Обратите внимание, что приведенное выше решение может печатать одно и то же слово несколько раз. Например, если мы добавим «SEEK» в словарь, он будет напечатан несколько раз. Чтобы избежать этого, мы можем использовать хеширование для отслеживания всех напечатанных слов.

В наборе 2 ниже мы обсудили оптимизированное решение на основе Trie:
Боггл | Набор 2 (с использованием Trie)

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

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

Boggle (Найти все возможные слова в доске символов) | Комплект 1

0.00 (0%) 0 votes