Проблема Boggle — интересная задача. И это не так сложно, если вы знакомы с алгоритмом DFS. Вы можете найти описания проблем по ссылке ниже.
https://www.geeksforgeeks.org/boggle-find-possible-words-board-characters/
В этой ссылке представлены решения C++, JAVA. Решение Python отсутствует. Я хотел бы предоставить код Python для решения этой проблемы.
"""
jimmy shen
Nov 22, 2019
reference
https://www.geeksforgeeks.org/boggle-find-possible-words-board-characters/
problems:
Boggle (Find all possible words in a board of characters) | Set 1
Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters. Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of same cell.
Example:
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
"""
class Boggle(object):
def find_words(self, words, boggle):
"""
input: words is the dictionary contains all possible words
boggle is the boggle
output: a list contains word_in_boggle for all possible words
"""
R, C = len(boggle), len(boggle[0])
def dfs(i, j, word, seen):
if i>=R or i<0 or j>=C or j<0:return False
if (i,j) in seen:return False
if not word:return True
if boggle[i][j] != word[0]:
return False
else:
seen.add((i, j))
return any(dfs(i+di, j+dj, word[1:], seen)
for di, dj in [(0,1),(1,0),(-1,0),(0,-1),(-1,-1),(1,-1),(-1,1),(1,1)])
def word_in_boggle(word):
for i in range(R):
for j in range(C):
if dfs(i,j,word,set()):
return True
return False
return [word_in_boggle(word) for word in words]
b = Boggle()
words = ["GEEKS", "FOR", "QUIZ", "GO"]
boggle = [['G', 'I', 'Z'],
['U', 'E', 'K'],
['Q', 'S', 'E']]
print(b.find_words(words, boggle))
