Given a dictionary of words and an M x N board where every cell has one character. Find all possible different words from the dictionary that can be formed by a sequence of adjacent characters on the board. We can move to any of 8 adjacent characters, but a word should not have multiple instances of the same cell.
Example 1:
Input: 
N = 1
dictionary = {"CAT"}
R = 3, C = 3
board = {{C,A,P},{A,N,D},{T,I,E}}
Output:
CAT
Explanation: 
C A P
A N D
T I E
Words we got is denoted using same color.
Example 2:
Input:
N = 4
dictionary = {"GEEKS","FOR","QUIZ","GO"}
R = 3, C = 3 
board = {{G,I,Z},{U,E,K},{Q,S,E}}
Output:
GEEKS QUIZ
Explanation: 
G I Z
U E K
Q S E 
Words we got is denoted using same color.
Your task:
You don’t need to read input or print anything. Your task is to complete the function wordBoggle() which takes the dictionary contaning N space-separated strings and R*C board as input parameters and returns a list of words that exist on the board (NOTE: All words returned must be different even it occurs multiple times in the dictionary).
Expected Time Complexity: O(4^(N^2))
Expected Auxiliary Space: O(N^2)
Constraints:
1 ≤ N ≤ 15
1 ≤ R, C ≤ 50
1 ≤ length of Word ≤ 60
All words of Dictionary and all characters of board are in uppercase letters from 'A' to 'Z'

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Graph traversal

String algorithms

Complete search

Data structures

Starter code: #User function Template for python3

class Solution:
    def wordBoggle(self,board,dictionary):
        # return list of words(str) found in the board

Solutions:
class Solution:

	def find(self, board, word):
		visited = [[False for i in range(len(board[0]))] for j in range(len(board))]

		def dfs(r, c, pos):
			if pos == len(word):
				return True
			if 0 <= r < len(board) and 0 <= c < len(board[0]) and (visited[r][c] == False) and (board[r][c] == word[pos]):
				visited[r][c] = True
				if dfs(r + 1, c, pos + 1) or dfs(r, c + 1, pos + 1) or dfs(r - 1, c, pos + 1) or dfs(r, c - 1, pos + 1) or dfs(r + 1, c + 1, pos + 1) or dfs(r + 1, c - 1, pos + 1) or dfs(r - 1, c + 1, pos + 1) or dfs(r - 1, c - 1, pos + 1):
					return True
				visited[r][c] = False
			return False
		indx = 0
		for i in range(len(board)):
			for j in range(len(board[0])):
				if board[i][j] == word[indx]:
					if dfs(i, j, indx):
						return True
		return False

	def wordBoggle(self, board, dictionary):
		res = []
		for i in range(len(dictionary)):
			word = dictionary[i]
			if self.find(board, word):
				res.append(word)
		return list(set(res))


from queue import Queue

class Node:

	def __init__(self, val):
		self.val = val
		self.children = [None for _ in range(26)]
		self.eow = False

	def isEnd(self):
		return self.eow

	def setChild(self, i, node):
		self.children[i] = node

	def getChild(self, i):
		return self.children[i]

class Trie:

	def __init__(self):
		self.root = Node(-1)

	def insert(self, word, node=None, i=0):
		if node is None:
			node = self.root
		c = word[i]
		o = ord(c) - ord('A')
		if node.getChild(o) is None:
			node.setChild(o, Node(c))
		if i < len(word) - 1:
			self.insert(word, node.getChild(o), i + 1)
		else:
			node.getChild(o).eow = True

	def printVal(self, node=None, prefix=' '):
		if node is None:
			node = self.root
		print(prefix, node.val, node.eow)
		for c in node.children:
			if c is not None:
				self.printVal(c, prefix + ' ')

class Solution:
	adjs = [1, -1, 1, 0, -1, -1, 0, 1, 1]

	def wordBoggle(self, board, dictionary):
		R = len(board)
		C = len(board[0])
		trie = Trie()
		res = set()
		for word in dictionary:
			trie.insert(word)
		inPath = [[False for _ in range(C)] for _ in range(R)]
		for i in range(R):
			for j in range(C):
				self.dfs(i, j, trie.root, board, inPath, res)
		return list(res)

	def dfs(self, i, j, node, board, inPath, res, stk=[]):
		c = board[i][j]
		o = ord(c) - ord('A')
		if node.getChild(o) is None:
			return
		stk.append(c)
		if node.getChild(o).isEnd():
			res.add(''.join(stk))
		inPath[i][j] = True
		for k in range(8):
			(ad_i, ad_j) = (i + self.adjs[k], j + self.adjs[k + 1])
			if ad_i < 0 or ad_i == len(board) or ad_j < 0 or (ad_j == len(board[0])):
				continue
			elif inPath[ad_i][ad_j]:
				continue
			self.dfs(ad_i, ad_j, node.getChild(o), board, inPath, res, stk)
		stk.pop()
		inPath[i][j] = False


class Solution:

	def wordBoggle(self, board, dicti):

		def func(n, m, dicti, board, ind1, ind2, stri, ind, vis):
			if ind == len(stri):
				return True
			if ind1 < 0 or ind2 < 0 or ind1 >= n or (ind2 >= m) or (board[ind1][ind2] != stri[ind]) or (vis[ind1][ind2] != 0):
				return False
			vis[ind1][ind2] = 1
			l1 = func(n, m, dicti, board, ind1 - 1, ind2, stri, ind + 1, vis)
			l2 = func(n, m, dicti, board, ind1 + 1, ind2, stri, ind + 1, vis)
			l3 = func(n, m, dicti, board, ind1, ind2 - 1, stri, ind + 1, vis)
			l4 = func(n, m, dicti, board, ind1, ind2 + 1, stri, ind + 1, vis)
			l5 = func(n, m, dicti, board, ind1 - 1, ind2 - 1, stri, ind + 1, vis)
			l6 = func(n, m, dicti, board, ind1 - 1, ind2 + 1, stri, ind + 1, vis)
			l7 = func(n, m, dicti, board, ind1 + 1, ind2 - 1, stri, ind + 1, vis)
			l8 = func(n, m, dicti, board, ind1 + 1, ind2 + 1, stri, ind + 1, vis)
			vis[ind1][ind2] = 0
			return l1 or l2 or l3 or l4 or l5 or l6 or l7 or l8
		dicti = list(set(dicti))
		n = len(board)
		m = len(board[0])
		vis = [[0 for i in range(m + 1)] for j in range(n)]
		li = []
		for i in dicti:
			for j in range(n):
				s2 = False
				for k in range(m):
					if board[j][k] == i[0]:
						kk = func(n, m, dicti, board, j, k, i, 0, vis)
						if kk:
							li.append(i)
							s2 = True
							break
				if s2:
					s1 = True
					break
		return li


class Solution:

	def bfs(self, i, j, k, n, m, l, board, visited, word):
		if k == l:
			return True
		dx = [0, 0, 1, -1, 1, 1, -1, -1]
		dy = [1, -1, 0, 0, -1, 1, 1, -1]
		for ind in range(8):
			(x, y) = (i + dx[ind], j + dy[ind])
			if x >= 0 and x < n and (y >= 0) and (y < m) and (board[x][y] == word[k]):
				char = board[x][y]
				board[x][y] = ''
				if self.bfs(x, y, k + 1, n, m, l, board, visited, word):
					board[x][y] = char
					return True
				board[x][y] = char
		return False

	def wordBoggle(self, board, dictionary):
		res = []
		(n, m) = (len(board), len(board[0]))
		for word in dictionary:
			l = len(word)
			for i in range(n):
				for j in range(m):
					if board[i][j] == word[0]:
						visited = [[0] * m for i in range(n)]
						board[i][j] = ''
						if self.bfs(i, j, 1, n, m, l, board, visited, word) and word not in res:
							res.append(word)
						board[i][j] = word[0]
		res.sort()
		return res


from collections import defaultdict

class Solution:

	def wordBoggle(self, board, dictionary):
		n = len(board)
		m = len(board[0])
		store = defaultdict(lambda : [])
		for i in range(n):
			for j in range(m):
				store[board[i][j]].append((i, j))
		output = []
		for word in dictionary:
			for (x, y) in store[word[0]]:
				output += self.wordSearch(word, 1, x, y, n, m, board, set())
		return sorted(set(output))

	def wordSearch(self, word, i, x, y, n, m, grid, path):
		if (x, y) in path:
			return []
		path.add((x, y))
		if i == len(word):
			return [word]
		output = []
		if x > 0 and grid[x - 1][y] == word[i]:
			output += self.wordSearch(word, i + 1, x - 1, y, n, m, grid, path.copy())
		if x < n - 1 and grid[x + 1][y] == word[i]:
			output += self.wordSearch(word, i + 1, x + 1, y, n, m, grid, path.copy())
		if y > 0 and grid[x][y - 1] == word[i]:
			output += self.wordSearch(word, i + 1, x, y - 1, n, m, grid, path.copy())
		if y < m - 1 and grid[x][y + 1] == word[i]:
			output += self.wordSearch(word, i + 1, x, y + 1, n, m, grid, path.copy())
		if x > 0 and y > 0 and (grid[x - 1][y - 1] == word[i]):
			output += self.wordSearch(word, i + 1, x - 1, y - 1, n, m, grid, path.copy())
		if x > 0 and y < m - 1 and (grid[x - 1][y + 1] == word[i]):
			output += self.wordSearch(word, i + 1, x - 1, y + 1, n, m, grid, path.copy())
		if x < n - 1 and y > 0 and (grid[x + 1][y - 1] == word[i]):
			output += self.wordSearch(word, i + 1, x + 1, y - 1, n, m, grid, path.copy())
		if x < n - 1 and y < m - 1 and (grid[x + 1][y + 1] == word[i]):
			output += self.wordSearch(word, i + 1, x + 1, y + 1, n, m, grid, path.copy())
		return output


def dfs(board, word, i, x, y, visited):
	if i >= len(word):
		return True
	if x < 0 or x >= len(board) or y < 0 or (y >= len(board[0])) or visited[x][y] or (board[x][y] != word[i]):
		return False
	visited[x][y] = True
	a1 = dfs(board, word, i + 1, x, y + 1, visited)
	a2 = dfs(board, word, i + 1, x, y - 1, visited)
	a3 = dfs(board, word, i + 1, x + 1, y, visited)
	a4 = dfs(board, word, i + 1, x - 1, y, visited)
	a5 = dfs(board, word, i + 1, x + 1, y + 1, visited)
	a6 = dfs(board, word, i + 1, x - 1, y + 1, visited)
	a7 = dfs(board, word, i + 1, x + 1, y - 1, visited)
	a8 = dfs(board, word, i + 1, x - 1, y - 1, visited)
	visited[x][y] = False
	if a1 or a2 or a3 or a4 or a5 or a6 or a7 or a8:
		return True
	return False

class Solution:

	def wordBoggle(self, board, dictionary):
		res = []
		for word in dictionary:
			visited = [[0] * len(board[0]) for i in range(len(board))]
			flag = False
			for i in range(len(board)):
				for j in range(len(board[0])):
					if board[i][j] == word[0]:
						if dfs(board, word, 0, i, j, visited):
							res.append(word)
							flag = True
							break
				if flag:
					break
		res = set(res)
		res = list(res)
		return res


class Solution:

	def wordBoggle(self, board, dictionary):
		dir = [[1, 0], [0, 1], [-1, 0], [0, -1], [1, 1], [-1, 1], [1, -1], [-1, -1]]
		res = []

		def solve(r, c, word, i):
			if i == len(word):
				res.append(word)
				return
			for (j, k) in dir:
				(nr, nc) = (r + j, c + k)
				if nr < 0 or nc < 0 or nr >= len(board) or (nc >= len(board[0])) or (board[nr][nc] != word[i]):
					continue
				temp = board[r][c]
				board[r][c] = -1
				solve(nr, nc, word, i + 1)
				board[r][c] = temp
		for word in dictionary:
			for i in range(len(board)):
				for j in range(len(board[0])):
					if word not in res:
						if board[i][j] == word[0]:
							solve(i, j, word, 1)
		return list(set(res))


def backtracking(dictionary, board):
	(r, c) = (len(board), len(board[0]))
	res = set()
	for word in dictionary:
		for i in range(r):
			state = False
			for j in range(c):
				if board[i][j] == word[0]:
					vis = set()
					vis.add((i, j))
					text = board[i][j]
					ind = 1
					if helper(word, board, r, c, i, j, vis, text, ind):
						res.add(word)
						state = True
						break
			if state:
				break
	res = list(res)
	return res

def helper(word, board, r, c, i, j, vis, text, ind):
	if text == word:
		return True
	for (ti, tj) in zip([1, -1, 0, 0, 1, -1, -1, 1], [0, 0, 1, -1, 1, 1, -1, -1]):
		(ni, nj) = (ti + i, tj + j)
		if len(text) < len(word) and (ni, nj) not in vis and isValid(ni, nj, r, c, board, word, ind):
			vis.add((ni, nj))
			if helper(word, board, r, c, ni, nj, vis, text + board[ni][nj], ind + 1):
				return True
			vis.remove((ni, nj))
	return False

def isValid(i, j, r, c, board, word, ind):
	if i >= 0 and i < r and (j >= 0) and (j < c) and (board[i][j] == word[ind]):
		return True
	return False

class Solution:

	def wordBoggle(self, board, dictionary):
		return backtracking(dictionary, board)


class Solution:

	def wordBoggle(self, board, dictionary):
		n = len(board)
		m = len(board[0])

		def dfs(board, s, i, j, idx):
			if i < 0 or i >= n or j < 0 or (j >= m):
				return False
			if s[idx] != board[i][j]:
				return False
			if idx == len(s) - 1:
				return True
			temp = board[i][j]
			board[i][j] = '*'
			a = dfs(board, s, i, j + 1, idx + 1)
			b = dfs(board, s, i, j - 1, idx + 1)
			c = dfs(board, s, i + 1, j, idx + 1)
			d = dfs(board, s, i - 1, j, idx + 1)
			e = dfs(board, s, i + 1, j + 1, idx + 1)
			f = dfs(board, s, i - 1, j + 1, idx + 1)
			g = dfs(board, s, i + 1, j - 1, idx + 1)
			h = dfs(board, s, i - 1, j - 1, idx + 1)
			board[i][j] = temp
			return a or b or c or e or f or g or h or d
		store = set()
		for i in range(n):
			for j in range(m):
				for word in dictionary:
					if dfs(board, word, i, j, 0):
						store.add(word)
		return list(store)


class Solution:

	def wordBoggle(self, board, dictionary):
		ROWS = len(board)
		COLS = len(board[0])

		def dfs(board, i, j, word, ind, visited):
			if ind == len(word):
				return True
			if i < 0 or j < 0 or i >= ROWS or (j >= COLS) or visited[i][j]:
				return False
			visited[i][j] = True
			if word[ind] == board[i][j]:
				dx = [1, -1, 0, 0, 1, 1, -1, -1]
				dy = [0, 0, 1, -1, -1, 1, 1, -1]
				for k in range(8):
					x = i + dx[k]
					y = j + dy[k]
					if dfs(board, x, y, word, ind + 1, visited):
						return True
			visited[i][j] = False
			return False

		def checker(word, board, visited):
			start = word[0]
			for i in range(ROWS):
				for j in range(COLS):
					if board[i][j] == start:
						if dfs(board, i, j, word, 0, visited):
							return True
			return False
		found = set()
		for word in dictionary:
			visited = []
			for i in range(ROWS):
				visited.append([False] * COLS)
			if checker(word, board, visited):
				found.add(word)
		return list(found)


def dfs(board, r, c, word, wi, tu, visited):
	(a, b) = tu
	if wi == len(word) - 1:
		return True
	visited[a][b] = True
	groups = [(-1, -1), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 1), (1, 0), (-1, 0)]
	for g in groups:
		(i, j) = g
		if a + i >= 0 and a + i < r and (b + j >= 0) and (b + j < c) and (not visited[a + i][b + j]) and (word[wi + 1] == board[a + i][b + j]) and dfs(board, r, c, word, wi + 1, (a + i, b + j), visited):
			return True
	visited[a][b] = False
	return False

def util(board, word):
	(r, c) = (len(board), len(board[0]))
	for i in range(r):
		for j in range(c):
			if board[i][j] == word[0]:
				visited = [[False] * c for i in range(r)]
				if dfs(board, r, c, word, 0, (i, j), visited):
					return True
	return False

class Solution:

	def wordBoggle(self, board, dictionary):
		ans = []
		for word in dictionary:
			if util(board, word):
				ans.append(word)
		return list(set(ans))


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Solution:

	def __init__(self):
		self.root = TrieNode()
		self.tempx = [0, 0, -1, 1, 1, -1, -1, 1]
		self.tempy = [1, -1, 0, 0, 1, -1, 1, -1]
		self.ans = set()

	def wordBoggle(self, board, dictionary):
		for word in dictionary:
			self.insertTrie(self.root, word)
		m = len(board)
		n = len(board[0])
		visited = [[False for _ in range(n)] for _ in range(m)]
		for i in range(m):
			for j in range(n):
				char = board[i][j]
				index = ord(char) - ord('A')
				node = self.root.children[index]
				if node:
					visited[i][j] = True
					self.dfs(node, visited, i, j, board, char)
					visited[i][j] = False
		return list(self.ans)

	def dfs(self, node, visited, x, y, board, tempstr):
		if node.isEndOfWord:
			self.ans.add(tempstr)
		for i in range(26):
			if node.children[i]:
				ch = chr(ord('A') + i)
				for j in range(8):
					newx = x + self.tempx[j]
					newy = y + self.tempy[j]
					if self.isValid(board, visited, newx, newy, ch):
						visited[newx][newy] = True
						self.dfs(node.children[i], visited, newx, newy, board, tempstr + ch)
						visited[newx][newy] = False

	def isValid(self, board, visited, x, y, ch):
		row = len(board)
		col = len(board[0])
		if x >= 0 and x < row and (y >= 0) and (y < col) and (visited[x][y] == False) and (ch == board[x][y]):
			return True
		else:
			return False

	def insertTrie(self, root, word):
		if len(word) == 0:
			root.isEndOfWord = True
			return
		node = TrieNode()
		index = ord(word[0]) - ord('A')
		if root.children[index]:
			node = root.children[index]
		else:
			root.children[index] = node
		self.insertTrie(node, word[1:])


class Node:

	def __init__(self):
		self.children = {}
		self.finish = False

class Trie:

	def __init__(self):
		self.root = Node()

	def addData(self, root, data):
		for i in data:
			if i not in root.children:
				root.children[i] = Node()
			root = root.children[i]
		root.finish = True

	def isPrefixFound(self, root, data, result):
		for i in data:
			if i in root.children:
				root = root.children[i]
			else:
				return False
		if root.finish == True:
			temp_ = ''.join(data)
			if temp_ not in result:
				result.append(temp_)
		return True

	def mainSearchFunction(self, root, matrix, visited, rowsize, columnsize, x, y, tempString, result):
		if visited[x][y] == 0:
			visited[x][y] = 1
			tempString.append(matrix[x][y])
			isprefix = self.isPrefixFound(root, tempString, result)
			if isprefix == True:
				self.searchHasStarted(root, matrix, visited, rowsize, columnsize, x, y, tempString, result)
			visited[x][y] = 0
			tempString.pop()

	def searchHasStarted(self, root, matrix, visited, rowsize, columnsize, x, y, tempString, result):
		if x - 1 >= 0:
			self.mainSearchFunction(root, matrix, visited, rowsize, columnsize, x - 1, y, tempString, result)
		if x + 1 < rowsize:
			self.mainSearchFunction(root, matrix, visited, rowsize, columnsize, x + 1, y, tempString, result)
		if y - 1 >= 0:
			self.mainSearchFunction(root, matrix, visited, rowsize, columnsize, x, y - 1, tempString, result)
		if y + 1 < columnsize:
			self.mainSearchFunction(root, matrix, visited, rowsize, columnsize, x, y + 1, tempString, result)
		if x - 1 >= 0 and y - 1 >= 0:
			self.mainSearchFunction(root, matrix, visited, rowsize, columnsize, x - 1, y - 1, tempString, result)
		if x - 1 >= 0 and y + 1 < columnsize:
			self.mainSearchFunction(root, matrix, visited, rowsize, columnsize, x - 1, y + 1, tempString, result)
		if x + 1 < rowsize and y - 1 >= 0:
			self.mainSearchFunction(root, matrix, visited, rowsize, columnsize, x + 1, y - 1, tempString, result)
		if x + 1 < rowsize and y + 1 < columnsize:
			self.mainSearchFunction(root, matrix, visited, rowsize, columnsize, x + 1, y + 1, tempString, result)

class Solution:

	def wordBoggle(self, matrix, words):
		t = Trie()
		row = len(matrix)
		column = len(matrix[0])
		visited = [[0 for i in range(column)] for i in range(row)]
		result = []
		tempString = []
		for i in words:
			t.addData(t.root, i)
		for i in range(len(matrix)):
			for j in range(len(matrix[i])):
				fastResult = t.isPrefixFound(t.root, matrix[i][j], result)
				if fastResult == True:
					visited[i][j] = 1
					tempString.append(matrix[i][j])
					t.searchHasStarted(t.root, matrix, visited, row, column, i, j, tempString, result)
					visited[i][j] = 0
					tempString.pop()
		return sorted(result)


class Solution:

	def wordBoggle(self, board, dictionary):

		def isvalid(x1, y1):
			return x1 >= 0 and x1 < ROWS and (y1 >= 0) and (y1 < COLS)

		def check(x, y, index):
			visited.add((x, y))
			if index == len(word) - 1:
				visited.remove((x, y))
				return True
			for (X, Y) in moves:
				if isvalid(x + X, y + Y) and (x + X, y + Y) not in visited and (word[index + 1] == board[x + X][y + Y]) and check(x + X, y + Y, index + 1):
					visited.remove((x, y))
					return True
			visited.remove((x, y))
			return False
		moves = ((1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1))
		visited = set()
		words = []
		(ROWS, COLS) = (len(board), len(board[0]))
		for i in range(ROWS):
			for j in range(COLS):
				k = 0
				while k < len(dictionary):
					if dictionary[k][0] == board[i][j] and dictionary[k] not in words:
						word = dictionary[k]
						if check(i, j, 0):
							words.append(word)
							dictionary.remove(word)
							k -= 1
					k += 1
		return words


class TrieNode:

	def __init__(self):
		self.child = {}
		self.last = False

	def insert(self, word):
		curr = self
		for i in word:
			if i not in curr.child:
				curr.child[i] = TrieNode()
			curr = curr.child[i]
		curr.last = True

class Solution:

	def wordBoggle(self, board, dictionary):
		root = TrieNode()
		for i in dictionary:
			root.insert(i)

		def dfs(i, j, node, curr, res):
			if node.last:
				res.append(curr)
				node.last = False
			if i < 0 or i >= r or j < 0 or (j >= c) or (board[i][j] not in node.child):
				return
			tmp = board[i][j]
			board[i][j] = '#'
			for (a, b) in [(1, 0), (-1, 0), (0, 1), (0, -1), (-1, -1), (1, -1), (-1, 1), (1, 1)]:
				x = i + a
				y = j + b
				dfs(x, y, node.child[tmp], curr + tmp, res)
			board[i][j] = tmp
		res = []
		(r, c) = (len(board), len(board[0]))
		for i in range(r):
			for j in range(c):
				dfs(i, j, root, '', res)
		return res


class Node:

	def __init__(self):
		self.link = dict()
		self.end = False

class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, word):
		tem = self.root
		for i in word:
			if i not in tem.link:
				tem.link[i] = Node()
			tem = tem.link[i]
		tem.end = True

class Solution:

	def wordBoggle(self, board, dictionary):
		Root = Trie()
		for word in dictionary:
			Root.insert(word)
		ans = set()
		n = len(board)
		m = len(board[0])

		def dfs(i, j, n, m, s, ans, nod, vis):
			vis.add((i, j))
			s += board[i][j]
			nod = nod.link[s[-1]]
			if nod.end == True:
				ans.add(s)
			tem = [-1, 0, 1]
			for p in tem:
				for q in tem:
					if not (p == 0 and q == 0):
						ne = i + p
						qe = j + q
						if ne > -1 and qe > -1 and (ne < n) and (qe < m) and (board[ne][qe] in nod.link) and ((ne, qe) not in vis):
							dfs(ne, qe, n, m, s, ans, nod, vis)
			vis.discard((i, j))
		for i in range(n):
			for j in range(m):
				if board[i][j] in Root.root.link:
					dfs(i, j, n, m, '', ans, Root.root, set())
		return list(ans)


class Solution:

	def wordBoggle(self, board, dictionary):

		class TrieNode:

			def __init__(self):
				self.child = {}
				self.Eow = False

		def insert(word, Trie):
			for w in word:
				if w not in Trie.child:
					Trie.child[w] = TrieNode()
				Trie = Trie.child[w]
			Trie.Eow = True

		def dfs(r, c, Trie, V, path):
			if Trie.Eow:
				res.append(path)
				Trie.Eow = False
			V.add(tuple((r, c)))
			for ch in exp:
				(x, y) = (ch[0] + r, ch[1] + c)
				if 0 <= x < L and 0 <= y < W and (board[x][y] in Trie.child) and ((x, y) not in V):
					path = path + board[x][y]
					dfs(x, y, Trie.child[board[x][y]], V, path)
					path = path[:-1]
			V.discard(tuple((r, c)))
		Trie = TrieNode()
		for word in dictionary:
			insert(word, Trie)
		res = []
		L = len(board)
		W = len(board[0])
		exp = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
		for r in range(L):
			for c in range(W):
				if board[r][c] in Trie.child:
					V = set()
					dfs(r, c, Trie.child[board[r][c]], V, '' + board[r][c])
		return res


class Solution:

	def wordBoggle(self, board, dictionary):
		n = len(board)
		m = len(board[0])
		l = []
		s = {}
		for word in dictionary:
			if word in s:
				continue
			s[word] = 1
			k = len(word)
			f = 0
			for i in range(n):
				for j in range(m):
					if board[i][j] == word[0]:

						def dfs(i, j, c):
							if c == k:
								return True
							if i < 0 or j < 0 or i >= n or (j >= m):
								return False
							if board[i][j] != word[c]:
								return False
							temp = board[i][j]
							board[i][j] = '*'
							g = dfs(i + 1, j, c + 1) or dfs(i - 1, j, c + 1) or dfs(i, j + 1, c + 1) or dfs(i, j - 1, c + 1) or dfs(i - 1, j + 1, c + 1) or dfs(i + 1, j + 1, c + 1) or dfs(i + 1, j - 1, c + 1) or dfs(i - 1, j - 1, c + 1)
							board[i][j] = temp
							return g
						if dfs(i, j, 0):
							f = 1
							break
				if f == 1:
					l.append(word)
					break
		return l


class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, st):
		curr = self.root
		for i in range(len(st)):
			if curr.childs[ord(st[i]) - ord('A')] == None:
				curr.childs[ord(st[i]) - ord('A')] = Node()
			curr = curr.childs[ord(st[i]) - ord('A')]
		curr.s = st

class Node:

	def __init__(self):
		self.childs = [None] * 26
		self.s = ''

class Solution:

	def wordBoggle(self, board, dictionary):

		def dfs(board, i, j, root, ans):
			if i < 0 or j < 0 or i >= len(board) or (j >= len(board[0])) or (visited[i][j] == True):
				return
			if root.childs[ord(board[i][j]) - ord('A')] == None:
				return
			child = root.childs[ord(board[i][j]) - ord('A')]
			if child.s != None and child.s != '':
				ans.add(child.s)
			visited[i][j] = True
			for m in range(len(move)):
				dfs(board, i + move[m][0], j + move[m][1], child, ans)
			visited[i][j] = False
		move = [[0, 1], [1, 0], [0, -1], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]]
		visited = [[False for i in range(len(board[0]))] for j in range(len(board))]
		t = Trie()
		for s in dictionary:
			t.insert(s)
		ans = set()
		root = t.root
		for i in range(len(board)):
			for j in range(len(board[0])):
				dfs(board, i, j, root, ans)
		ans = list(ans)
		return ans


class Solution:

	def wordBoggle(self, board, dictionary):

		def f(i, j, n, m, ind, word, board, vis):
			if i < 0 or i >= n or j < 0 or (j >= m) or vis[i][j]:
				return False
			if board[i][j] == word[ind]:
				if ind == len(word) - 1:
					return True
				vis[i][j] = 1
				if f(i + 1, j, n, m, ind + 1, word, board, vis) or f(i - 1, j, n, m, ind + 1, word, board, vis) or f(i, j + 1, n, m, ind + 1, word, board, vis) or f(i, j - 1, n, m, ind + 1, word, board, vis) or f(i + 1, j + 1, n, m, ind + 1, word, board, vis) or f(i + 1, j - 1, n, m, ind + 1, word, board, vis) or f(i - 1, j + 1, n, m, ind + 1, word, board, vis) or f(i - 1, j - 1, n, m, ind + 1, word, board, vis):
					return True
				vis[i][j] = 0
			return False
		n = len(board)
		m = len(board[0])
		ans = set()
		for ele in dictionary:
			flag = 0
			for i in range(n):
				if flag:
					break
				for j in range(m):
					if board[i][j] == ele[0]:
						vis = [[0] * m for _ in range(n)]
						if f(i, j, n, m, 0, ele, board, vis):
							ans.add(ele)
							flag = 1
							break
		return list(ans)


class TrieNode:

	def __init__(self):
		self.children = {}
		self.isendWord = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, word: str) -> None:
		curr = self.root
		for i in word:
			if i not in curr.children:
				curr.children[i] = TrieNode()
			curr = curr.children[i]
		curr.isendWord = True

class Solution:

	def wordBoggle(self, board, words):
		trie = Trie()
		for word in words:
			trie.insert(word)
		rows = len(board)
		cols = len(board[0])
		res = set()
		vis = set()

		def dfs(i, j, node, word):
			if i < 0 or j < 0 or i == rows or (j == cols) or ((i, j) in vis) or (board[i][j] not in node.children):
				return False
			node = node.children[board[i][j]]
			word += board[i][j]
			vis.add((i, j))
			if node.isendWord:
				res.add(word)
			dfs(i + 1, j, node, word)
			dfs(i, j + 1, node, word)
			dfs(i - 1, j, node, word)
			dfs(i, j - 1, node, word)
			dfs(i + 1, j + 1, node, word)
			dfs(i + 1, j - 1, node, word)
			dfs(i - 1, j + 1, node, word)
			dfs(i - 1, j - 1, node, word)
			vis.remove((i, j))
		for i in range(rows):
			for j in range(cols):
				dfs(i, j, trie.root, '')
		return list(res)


class Solution:

	def wordBoggle(self, board, dictionary):

		def dfs(board, word, v, i, j, indx):
			if indx == len(word):
				return True
			if i >= 0 and i < len(board) and (j >= 0) and (j < len(board[0])) and (v[i][j] == False) and (board[i][j] == word[indx]):
				v[i][j] = True
				if dfs(board, word, v, i - 1, j - 1, indx + 1) or dfs(board, word, v, i - 1, j, indx + 1) or dfs(board, word, v, i - 1, j + 1, indx + 1) or dfs(board, word, v, i, j - 1, indx + 1) or dfs(board, word, v, i, j + 1, indx + 1) or dfs(board, word, v, i + 1, j - 1, indx + 1) or dfs(board, word, v, i + 1, j, indx + 1) or dfs(board, word, v, i + 1, j + 1, indx + 1):
					return True
				v[i][j] = False
			return False

		def exist(board, word):
			r = len(board)
			c = len(board[0])
			v = [[False for i in range(c)] for j in range(r)]
			for i in range(r):
				for j in range(c):
					if board[i][j] == word[0]:
						if dfs(board, word, v, i, j, 0):
							return True
			return False
		l = []
		for i in dictionary:
			if exist(board, i):
				if i not in l:
					l.append(i)
		return l
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		dictionary = [x for x in input().strip().split()]
		line = input().strip().split()
		R = int(line[0])
		C = int(line[1])
		board = []
		for _ in range(R):
			board.append([x for x in input().strip().split()])
		obj = Solution()
		found = obj.wordBoggle(board, dictionary)
		if len(found) is 0:
			print(-1)
			continue
		found.sort()
		for i in found:
			print(i, end=' ')
		print()


class Solution:

	def wordBoggle(self, board, dictionary):
		n = len(board)
		m = len(board[0])

		def solve(i, j, word, index, size):
			count = 0
			if i >= 0 and j >= 0 and (i < n) and (j < m) and (word[index] == board[i][j]):
				ch = board[i][j]
				board[i][j] = '*'
				index += 1
				if index == size:
					count = 1
				else:
					count = solve(i - 1, j - 1, word, index, size)
					if count == 0:
						count = solve(i - 1, j, word, index, size)
					if count == 0:
						count = solve(i - 1, j + 1, word, index, size)
					if count == 0:
						count = solve(i, j - 1, word, index, size)
					if count == 0:
						count = solve(i, j + 1, word, index, size)
					if count == 0:
						count = solve(i + 1, j - 1, word, index, size)
					if count == 0:
						count = solve(i + 1, j, word, index, size)
					if count == 0:
						count = solve(i + 1, j + 1, word, index, size)
				board[i][j] = ch
			return count
		ans = []
		s = set()
		for i in range(n):
			for j in range(m):
				for word in dictionary:
					if word not in s:
						if solve(i, j, word, 0, len(word)) > 0:
							s.add(word)
							ans.append(word)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		dictionary = [x for x in input().strip().split()]
		line = input().strip().split()
		R = int(line[0])
		C = int(line[1])
		board = []
		for _ in range(R):
			board.append([x for x in input().strip().split()])
		obj = Solution()
		found = obj.wordBoggle(board, dictionary)
		if len(found) is 0:
			print(-1)
			continue
		found.sort()
		for i in found:
			print(i, end=' ')
		print()


class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, st):
		curr = self.root
		for i in range(len(st)):
			if curr.childs[ord(st[i]) - ord('A')] == None:
				curr.childs[ord(st[i]) - ord('A')] = Node()
			curr = curr.childs[ord(st[i]) - ord('A')]
		curr.s = st

class Node:

	def __init__(self):
		self.childs = [None] * 26
		self.s = ''

class Solution:

	def wordBoggle(self, board, dictionary):

		def dfs(board, i, j, root, ans):
			if i < 0 or j < 0 or i >= len(board) or (j >= len(board[0])) or (visited[i][j] == True):
				return
			if root.childs[ord(board[i][j]) - ord('A')] == None:
				return
			child = root.childs[ord(board[i][j]) - ord('A')]
			if child.s != None and child.s != '':
				ans.add(child.s)
			visited[i][j] = True
			for m in range(len(move)):
				dfs(board, i + move[m][0], j + move[m][1], child, ans)
			visited[i][j] = False
		move = [[0, 1], [1, 0], [0, -1], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]]
		visited = [[False for i in range(len(board[0]))] for j in range(len(board))]
		t = Trie()
		for s in dictionary:
			t.insert(s)
		ans = set()
		root = t.root
		for i in range(len(board)):
			for j in range(len(board[0])):
				dfs(board, i, j, root, ans)
		ans = list(ans)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		dictionary = [x for x in input().strip().split()]
		line = input().strip().split()
		R = int(line[0])
		C = int(line[1])
		board = []
		for _ in range(R):
			board.append([x for x in input().strip().split()])
		obj = Solution()
		found = obj.wordBoggle(board, dictionary)
		if len(found) is 0:
			print(-1)
			continue
		found.sort()
		for i in found:
			print(i, end=' ')
		print()


class TrieNode:

	def __init__(self):
		self.children = {}
		self.isWord = False

	def addWord(self, word):
		curr = self
		for c in word:
			if c not in curr.children:
				curr.children[c] = TrieNode()
			curr = curr.children[c]
		curr.isWord = True

class Solution:

	def wordBoggle(self, board, dictionary):
		root = TrieNode()
		for w in dictionary:
			root.addWord(w)
		(rows, cols) = (len(board), len(board[0]))
		(result, visit) = (set(), set())

		def dfs(r, c, node, word):
			if r < 0 or c < 0 or r == rows or (c == cols) or ((r, c) in visit) or (board[r][c] not in node.children):
				return
			visit.add((r, c))
			node = node.children[board[r][c]]
			word += board[r][c]
			if node.isWord:
				result.add(word)
			dfs(r - 1, c, node, word)
			dfs(r + 1, c, node, word)
			dfs(r, c - 1, node, word)
			dfs(r, c + 1, node, word)
			dfs(r + 1, c - 1, node, word)
			dfs(r + 1, c + 1, node, word)
			dfs(r - 1, c - 1, node, word)
			dfs(r - 1, c + 1, node, word)
			visit.remove((r, c))
		for r in range(rows):
			for c in range(cols):
				dfs(r, c, root, '')
		return list(result)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		dictionary = [x for x in input().strip().split()]
		line = input().strip().split()
		R = int(line[0])
		C = int(line[1])
		board = []
		for _ in range(R):
			board.append([x for x in input().strip().split()])
		obj = Solution()
		found = obj.wordBoggle(board, dictionary)
		if len(found) is 0:
			print(-1)
			continue
		found.sort()
		for i in found:
			print(i, end=' ')
		print()


class TrieNode:

	def __init__(self):
		self.children = {}
		self.end = False

class Solution:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, word, root):
		cur = root
		for c in word:
			if c not in cur.children:
				cur.children[c] = TrieNode()
			cur = cur.children[c]
		cur.end = True

	def dfs(self, i, j, board, cur, visited, word, ans):
		word += board[i][j]
		if cur.end:
			if word not in ans:
				ans.append(word)
		x = [[i + 1, j], [i + 1, j + 1], [i, j + 1], [i - 1, j], [i, j - 1], [i - 1, j - 1], [i + 1, j - 1], [i - 1, j + 1]]
		for k in range(8):
			a = x[k][0]
			b = x[k][1]
			if a >= 0 and a < len(board) and (b >= 0) and (b < len(board[0])):
				c = board[a][b]
				if visited[a][b] == 0 and c in cur.children:
					visited[a][b] = 1
					self.dfs(a, b, board, cur.children[c], visited, word, ans)
					visited[a][b] = 0
		return

	def wordBoggle(self, board, dictionary):
		cur = self.root
		for word in dictionary:
			self.insert(word, cur)
		word = ''
		visited = [[0 for i in range(len(board[0]))] for j in range(len(board))]
		ans = []
		for i in range(len(board)):
			for j in range(len(board[0])):
				if visited[i][j] == 0 and board[i][j] in cur.children:
					visited[i][j] = 1
					self.dfs(i, j, board, cur.children[board[i][j]], visited, word, ans)
					visited[i][j] = 0
					word = ''
		return ans


class Trie:

	def __init__(self):
		self.child = {}
		self.e = 0

	def add(self, word):
		cur = self
		for w in word:
			if w not in cur.child:
				cur.child[w] = Trie()
			cur = cur.child[w]
		cur.e = 1

class Solution:

	def wordBoggle(self, board, dic):
		root = Trie()
		for w in dic:
			root.add(w)
		vis = set()
		ans = set()
		(m, n) = (len(board), len(board[0]))

		def dfs(i, j, cur, p):
			if cur.e == 1:
				ans.add(p)
				if cur.child == {}:
					return
			vis.add((i, j))
			for (di, dj) in [(1, 0), (0, 1), (-1, 0), (0, -1), (1, -1), (-1, 1), (-1, -1), (1, 1)]:
				(x1, y1) = (i + di, j + dj)
				if 0 <= x1 < m and 0 <= y1 < n and ((x1, y1) not in vis) and (board[x1][y1] in cur.child):
					dfs(x1, y1, cur.child[board[x1][y1]], p + board[x1][y1])
			vis.remove((i, j))
		for i in range(m):
			for j in range(n):
				if board[i][j] in root.child:
					dfs(i, j, root.child[board[i][j]], board[i][j])
		return list(ans)


class Solution:

	def wordBoggle(self, board, dictionary):
		ans = []
		rows = len(board)
		cols = len(board[0])

		def dfs(r, c, i, wor, path):
			if i == len(wor):
				return True
			if r < 0 or c < 0 or r >= rows or (c >= cols) or (wor[i] != board[r][c]) or ((r, c) in path):
				return False
			path.add((r, c))
			res = dfs(r + 1, c, i + 1, wor, path) or dfs(r - 1, c, i + 1, wor, path) or dfs(r - 1, c - 1, i + 1, wor, path) or dfs(r + 1, c + 1, i + 1, wor, path) or dfs(r, c + 1, i + 1, wor, path) or dfs(r, c - 1, i + 1, wor, path) or dfs(r - 1, c + 1, i + 1, wor, path) or dfs(r + 1, c - 1, i + 1, wor, path)
			path.remove((r, c))
			return res
		for wor in dictionary:
			path = set()
			for r in range(rows):
				for c in range(cols):
					if dfs(r, c, 0, wor, path) and wor not in ans:
						ans.append(wor)
		return ans


class Solution:

	def wordBoggle(self, board, dictionary):
		ans = set()
		for word in dictionary:
			self.searchWord(ans, word, board)
		return list(ans)

	def searchWord(self, ans, word, board):
		visited = [[False] * len(board[0]) for _ in range(len(board))]
		idx = 0
		for i in range(len(board)):
			for j in range(len(board[0])):
				if board[i][j] == word[0]:
					self.solver(board, dictionary, ans, visited, i, j, '', 0, word)

	def solver(self, board, dictionary, ans, visited, i, j, ssf, idx, word):
		if i < 0 or j < 0 or i >= len(board) or (j >= len(board[0])) or (visited[i][j] == True) or (board[i][j] != word[idx]):
			return
		if idx >= len(word):
			return
		if idx == len(word) - 1:
			ans.add(word)
			return
		visited[i][j] = True
		self.solver(board, dictionary, ans, visited, i - 1, j, ssf + board[i][j], idx + 1, word)
		self.solver(board, dictionary, ans, visited, i - 1, j + 1, ssf + board[i][j], idx + 1, word)
		self.solver(board, dictionary, ans, visited, i, j + 1, ssf + board[i][j], idx + 1, word)
		self.solver(board, dictionary, ans, visited, i + 1, j + 1, ssf + board[i][j], idx + 1, word)
		self.solver(board, dictionary, ans, visited, i + 1, j, ssf + board[i][j], idx + 1, word)
		self.solver(board, dictionary, ans, visited, i + 1, j - 1, ssf + board[i][j], idx + 1, word)
		self.solver(board, dictionary, ans, visited, i, j - 1, ssf + board[i][j], idx + 1, word)
		self.solver(board, dictionary, ans, visited, i - 1, j - 1, ssf + board[i][j], idx + 1, word)
		visited[i][j] = False


class Solution:

	def recur_util(self, cur_ind, board, word):
		res = False
		visited = [[False] * len(board[0]) for _ in range(len(board))]
		opts = [[0, 1], [1, 0], [1, 1], [0, -1], [-1, 0], [-1, -1], [1, -1], [-1, 1]]

		def recur(x, y, visited, w_ind, word):
			if x < 0 or y < 0 or x >= len(board) or (y >= len(board[0])):
				return
			if visited[x][y]:
				return
			if word[w_ind] == board[x][y]:
				if w_ind >= len(word) - 1:
					nonlocal res
					res = True
					return
				visited[x][y] = True
				for opt in opts:
					recur(x + opt[0], y + opt[1], visited, w_ind + 1, word)
				visited[x][y] = False
			else:
				return
		recur(cur_ind[0], cur_ind[1], visited, 0, word)
		return res

	def wordBoggle(self, board, dictionary):
		res = []
		for word in set(dictionary):
			found = False
			for i in range(len(board)):
				for j in range(len(board[0])):
					if board[i][j] == word[0]:
						if self.recur_util((i, j), board, word):
							res.append(word)
							found = True
							break
				if found:
					break
		return res


class TrieNode:

	def __init__(self):
		self.children = dict()
		self.isLeaf = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, word):
		current = self.root
		for char in word:
			if char not in current.children:
				current.children[char] = TrieNode()
			current = current.children[char]
		current.isLeaf = True

class Solution:

	def wordBoggle(self, board, dictionary):
		trie = Trie()
		for word in dictionary:
			trie.insert(word)
		(ROWS, COLS) = (len(board), len(board[0]))
		result = []
		visited = set()

		def dfs(row, col, node, parent_str):
			if row < 0 or row >= ROWS or col < 0 or (col >= COLS) or ((row, col) in visited) or (board[row][col] not in node.children):
				return
			visited.add((row, col))
			char = board[row][col]
			newNode = node.children[char]
			newParentStr = parent_str + char
			if newNode.isLeaf:
				result.append(newParentStr)
				newNode.isLeaf = False
			dfs(row + 1, col, newNode, newParentStr)
			dfs(row, col + 1, newNode, newParentStr)
			dfs(row - 1, col, newNode, newParentStr)
			dfs(row, col - 1, newNode, newParentStr)
			dfs(row - 1, col + 1, newNode, newParentStr)
			dfs(row + 1, col - 1, newNode, newParentStr)
			dfs(row - 1, col - 1, newNode, newParentStr)
			dfs(row + 1, col + 1, newNode, newParentStr)
			visited.remove((row, col))
		for r in range(ROWS):
			for c in range(COLS):
				dfs(r, c, trie.root, '')
		return result


class Solution:

	def wordBoggle(self, board, dictionary):

		def dfs(i, j, k, word, vis):
			vis[i][j] = True
			if k == len(word):
				return True
			for (x, y) in directions:
				if 0 <= i + x < n and 0 <= j + y < m and (board[i + x][j + y] == word[k]) and (vis[i + x][j + y] == False):
					if dfs(i + x, j + y, k + 1, word, vis):
						return True
			vis[i][j] = False
			return False

		def find_word(word):
			for i in range(n):
				for j in range(m):
					if board[i][j] == word[0]:
						vis = [[False] * m for _ in range(n)]
						if dfs(i, j, 1, word, vis):
							return True
			return False
		n = len(board)
		m = len(board[0])
		directions = [[0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1]]
		ans = []
		for word in dictionary:
			if find_word(word) and word not in ans:
				ans.append(word)
		return ans


class Solution:

	def wordBoggle(self, board, dictionary):
		(m, n) = (len(board), len(board[0]))
		output = []

		def possible(i, j, m, n):
			return i >= 0 and j >= 0 and (i < m) and (j < n)

		def solver(t, board, word, inx, m, n):
			if inx == len(word):
				if word not in output:
					output.append(word)
					return True
				return False
			(i, j) = (t[0], t[1])
			visited[i][j] = True
			a = [-1, -1, 0, 1, 1, 1, 0, -1]
			b = [0, -1, -1, -1, 0, 1, 1, 1]
			for k in range(8):
				(r, c) = (i + a[k], j + b[k])
				if possible(r, c, m, n) and board[r][c] == word[inx] and (visited[r][c] == False):
					if solver([r, c], board, word, inx + 1, m, n):
						return True
			visited[i][j] = False
			return False
		for t in dictionary:
			word = t
			visited = [[False for i in range(n)] for j in range(m)]
			for i in range(m):
				for j in range(n):
					if word[0] == board[i][j] and visited[i][j] == False:
						solver([i, j], board, word, 1, m, n)
		return output


class Node:

	def __init__(self):
		self.chi = {}
		self.isla = False

class trie:

	def __init__(self):
		self.root = Node()

	def add(self, word):
		t = self.root
		for val in word:
			if t.chi.get(val) is None:
				t.chi[val] = Node()
			t = t.chi[val]
		t.isla = True

class Solution:

	def wordBoggle(self, board, dictionary):
		n = len(board)
		m = len(board[0])

		def isval(x, y, vis):
			if x < 0 or y < 0 or x >= n or (y >= m):
				return False
			return (x, y) not in vis
		dx = [1, 1, 1, -1, -1, -1, 0, 0]
		dy = [1, -1, 0, 1, -1, 0, 1, -1]

		def dfs(x, y, t, s, vis):
			vis.add((x, y))
			if t.isla:
				ans.add(s)
			for i in range(8):
				if isval(x + dx[i], y + dy[i], vis) and t.chi.get(board[x + dx[i]][y + dy[i]]):
					dfs(x + dx[i], y + dy[i], t.chi[board[x + dx[i]][y + dy[i]]], s + board[x + dx[i]][y + dy[i]], vis)
			vis.remove((x, y))
		gr = trie()
		for val in dictionary:
			gr.add(val)
		ans = set()
		vis = set()
		for i in range(n):
			for j in range(m):
				if gr.root.chi.get(board[i][j]) is not None:
					dfs(i, j, gr.root.chi[board[i][j]], board[i][j], vis)
		return list(ans)


class Solution:

	def wordBoggle(self, board, dictionary):

		def dfs(i, j, d):
			if d == w:
				return True
			visited[i][j] = True
			for k in range(8):
				if 0 <= i + a[k] < n and 0 <= j + b[k] < m and (board[i + a[k]][j + b[k]] == word[d]) and (not visited[i + a[k]][j + b[k]]):
					if dfs(i + a[k], j + b[k], d + 1):
						return True
			visited[i][j] = False
		n = len(board)
		m = len(board[0])
		a = [0, 0, 1, -1, 1, 1, -1, -1]
		b = [1, -1, 0, 0, 1, -1, 1, -1]
		ans = []
		for word in dictionary:
			c = 0
			w = len(word)
			visited = [[False for i in range(m)] for j in range(n)]
			if word in ans:
				continue
			for i in range(n):
				for j in range(m):
					if board[i][j] == word[0]:
						if dfs(i, j, 1):
							ans.append(word)
							c = 1
							break
				if c == 1:
					break
		return ans


class Solution:

	def wordBoggle(self, board, dictionary):
		N = len(board)
		M = len(board[0])
		visited = [[0 for _ in range(M)] for _ in range(N)]
		res = []
		words = set()
		for k in range(len(dictionary)):
			for i in range(N):
				for j in range(M):
					if board[i][j] == dictionary[k][0]:
						flag = self.DFS(board, dictionary[k], visited, N, M, i, j, 0)
						if flag == 1:
							words.add(dictionary[k])
							break
		words = list(words)
		return words

	def DFS(self, board, word, visited, n, m, x, y, idx):
		if idx == len(word):
			return 1
		if x >= n or x < 0 or y >= m or (y < 0):
			return 0
		if visited[x][y] == 1:
			return 0
		if board[x][y] != word[idx]:
			return 0
		visited[x][y] = 1
		flag = 0
		dx = [-1, -1, -1, 0, 0, 1, 1, 1]
		dy = [-1, 0, 1, -1, 1, -1, 0, 1]
		for i in range(8):
			xx = x + dx[i]
			yy = y + dy[i]
			flag |= self.DFS(board, word, visited, n, m, xx, yy, idx + 1)
		visited[x][y] = 0
		return flag


class Solution:

	def wordBoggle(self, board, dictionary):
		(n, m) = (len(board), len(board[0]))
		answers = []
		for word in dictionary:
			for i in range(n):
				for j in range(m):
					if board[i][j] == word[0]:
						visit = [[False] * m for _ in range(n)]
						visit[i][j] = True
						if self.check(board, word[1:], visit, i, j):
							answers.append(word)
						visit[i][j] = False
		return list(set(answers))

	def check(self, board, word, visit, i, j):
		if len(word) == 0:
			return True
		(n, m) = (len(board), len(board[0]))
		dx = [-1, -1, -1, 0, 0, 1, 1, 1]
		dy = [-1, 0, 1, -1, 1, -1, 0, 1]
		for k in range(8):
			_i = i + dx[k]
			_j = j + dy[k]
			if _i >= 0 and _i < n and (_j >= 0) and (_j < m):
				if visit[_i][_j] == False and board[_i][_j] == word[0]:
					visit[_i][_j] = True
					if self.check(board, word[1:], visit, _i, _j):
						return True
					visit[_i][_j] = False
		return False


from collections import defaultdict as dd

class Solution:

	def wordBoggle(self, board, dicti):
		d = dd(list)
		res = set()
		(R, C) = (len(board), len(board[0]))
		vis = [[False for _ in range(C)] for _ in range(R)]
		for i in range(R):
			for j in range(C):
				d[board[i][j]].append((i, j))

		def dfs(w, d, ind, r=None, c=None):
			if ind == len(w):
				return True
			ch = w[ind]
			t = d[ch]
			for (i, j) in t:
				if not r and (not c) and (ind == 0):
					if not vis[i][j]:
						vis[i][j] = True
						if dfs(w, d, ind + 1, i, j):
							vis[i][j] = False
							return True
						vis[i][j] = False
				else:
					dif = max(abs(i - r), abs(j - c))
					if dif < 2 and (not vis[i][j]):
						vis[i][j] = True
						if dfs(w, d, ind + 1, i, j):
							vis[i][j] = False
							return True
						vis[i][j] = False
			return False
		for wrd in dicti:
			if dfs(wrd, d, 0):
				res.add(wrd)
		return list(res)


class Solution:

	def createTrie(self, words):
		trie = {}
		for word in words:
			root = trie
			for c in word:
				if c not in root:
					root[c] = {}
				root = root[c]
			root['#'] = '#'
		return trie

	def wordBoggle(self, board, dictionary):
		trie = self.createTrie(dictionary)
		self.res = set()
		for row in range(len(board)):
			for col in range(len(board[0])):
				if board[row][col] in trie:
					self.dfs(board, row, col, '', trie)
		return list(self.res)

	def inBounds(self, board, row, col):
		if row < 0 or col < 0 or row == len(board) or (col == len(board[0])):
			return False
		return True

	def dfs(self, board, row, col, word, trie):
		currChar = board[row][col]
		newTrie = trie[currChar]
		newWord = word + currChar
		board[row][col] = ''
		for ch in newTrie:
			if ch == '#':
				self.res.add(newWord)
			else:
				for (x, y) in [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]:
					if self.inBounds(board, row + x, col + y) and ch == board[row + x][col + y]:
						self.dfs(board, row + x, col + y, newWord, newTrie)
		board[row][col] = currChar


class Solution:
	dirs = [[1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1], [0, 1]]

	def on_board(self, i, j, board):
		return 0 <= i < len(board) and 0 <= j < len(board[0])

	def removeFromDict(self, dictionary, i, ch):
		new_dict = []
		for w in dictionary:
			if w[i] != ch:
				continue
			elif len(w) - 1 == i:
				self.ans.add(w)
			else:
				new_dict.append(w)
		return new_dict

	def dfs(self, i, j, dictionary, index):
		if len(dictionary) == 0:
			return
		for d in self.dirs:
			ni = i + d[0]
			nj = j + d[1]
			if self.on_board(ni, nj, self.board) and (not self.visited[ni][nj]):
				self.visited[ni][nj] = 1
				self.dfs(ni, nj, self.removeFromDict(dictionary, index, self.board[ni][nj]), index + 1)
				self.visited[ni][nj] = 0

	def wordBoggle(self, board, dictionary):
		self.board = board
		self.visited = [[0 for j in range(len(board[0]))] for i in range(len(board))]
		self.ans = set()
		for i in range(len(board)):
			for j in range(len(board[0])):
				self.visited[i][j] = 1
				ans = []
				self.dfs(i, j, self.removeFromDict(dictionary, 0, board[i][j]), 1)
				self.visited[i][j] = 0
		return list(self.ans)


class Solution:

	def wordBoggle(self, board, dictionary):

		def dfs(k, board, i, j, R, C):
			n = len(k)
			bool = False
			if k[0] == board[i][j] and n == 1:
				return True
			if k[0] == board[i][j]:
				temp = board[i][j]
				board[i][j] = '$'
				a = [[i - 1, j - 1], [i - 1, j], [i - 1, j + 1], [i, j - 1], [i, j + 1], [i + 1, j - 1], [i + 1, j], [i + 1, j + 1]]
				for x in a:
					if -1 < x[0] < R and -1 < x[1] < C:
						bool = bool or dfs(k[1:], board, x[0], x[1], R, C)
						if bool:
							board[i][j] = temp
							return True
				board[i][j] = temp
			return False
		res = []
		R = len(board)
		C = len(board[0])
		memo = {}
		for i in dictionary:
			if i[0] in memo:
				if i not in memo[i[0]]:
					memo[i[0]] += [i]
			else:
				memo[i[0]] = [i]
		for i in range(R):
			for j in range(C):
				if board[i][j] in memo:
					arr = []
					for k in memo[board[i][j]]:
						if dfs(k, board, i, j, R, C):
							res += [k]
						else:
							arr += [k]
					memo[board[i][j]] = arr
		return res


class Solution:

	def wordBoggle(self, g, d):
		r = len(g)
		c = len(g[0])
		dx = [-1, -1, -1, 0, 0, 1, 1, 1]
		dy = [-1, 0, 1, -1, 1, -1, 0, 1]

		def isSafe(x, y):
			return x >= 0 and y >= 0 and (x < r) and (y < c)

		def bfs(x, y, k, s):
			q = deque()
			n = len(s)
			q.append((x, y, k))
			vis = [[False for _ in range(c)] for _ in range(r)]
			vis[x][y] = True
			while q:
				(i, j, k) = q.popleft()
				k += 1
				if k >= n:
					return True
				for z in range(8):
					x = i + dx[z]
					y = j + dy[z]
					if isSafe(x, y) and vis[x][y] == False and (k < n) and (g[x][y] == s[k]):
						q.append((x, y, k))
						vis[x][y] = True
			return False

		def dfs(x, y, level, s):
			n = len(s)
			if level == n:
				return True
			if not isSafe(x, y):
				return False
			if g[x][y] == s[level]:
				t = g[x][y]
				g[x][y] = '#'
				res = dfs(x - 1, y, level + 1, s) or dfs(x + 1, y, level + 1, s) or dfs(x, y - 1, level + 1, s) or dfs(x, y + 1, level + 1, s) or dfs(x - 1, y + 1, level + 1, s) or dfs(x + 1, y + 1, level + 1, s) or dfs(x + 1, y - 1, level + 1, s) or dfs(x - 1, y - 1, level + 1, s)
				g[x][y] = t
				return res
			else:
				return False
		ans = []
		d1 = {}
		for k in d:
			d1[k] = False
		for i in range(r):
			for j in range(c):
				for k in d:
					if d1[k] == False and g[i][j] == k[0]:
						if dfs(i, j, 0, k):
							ans.append(k)
							d1[k] = True
		ans.sort()
		return ans


class Solution:

	def wordBoggle(self, board, dictionary):
		(n, m) = (len(board), len(board[0]))
		used = [[False for _ in range(m)] for _ in range(n)]
		l = []
		ls = set()

		def dfs(row, col, s, k):
			if len(s) <= k:
				return True
			flag = False
			if 0 <= row < n and 0 <= col < m and (not used[row][col]):
				if s[k] == board[row][col]:
					used[row][col] = True
					flag = flag or dfs(row + 1, col - 1, s, k + 1)
					flag = flag or dfs(row + 1, col, s, k + 1)
					flag = flag or dfs(row + 1, col + 1, s, k + 1)
					flag = flag or dfs(row, col - 1, s, k + 1)
					flag = flag or dfs(row, col + 1, s, k + 1)
					flag = flag or dfs(row - 1, col - 1, s, k + 1)
					flag = flag or dfs(row - 1, col, s, k + 1)
					flag = flag or dfs(row - 1, col + 1, s, k + 1)
					used[row][col] = False
			return flag
		for w in dictionary:
			if w in ls:
				continue
			for i in range(n):
				for j in range(m):
					if dfs(i, j, w, 0):
						l.append(w)
						ls.add(w)
						break
				else:
					continue
				break
		return l


def find_start(c, board):
	lst = []
	for i in range(len(board)):
		for j in range(len(board[0])):
			if board[i][j] == c:
				lst.append((i, j))
	return lst

class Solution:

	def solve(self, i, j, done, length, word, row, col, board, string):
		if done == length and string == word:
			self.result.append(word)
			self.found = True
			return
		if not self.found and j + 1 < col and (board[i][j + 1] == word[done]):
			board[i][j + 1] = ''
			self.solve(i, j + 1, done + 1, length, word, row, col, board, string + word[done])
			board[i][j + 1] = word[done]
		if not self.found and i + 1 < row and (j + 1 < col) and (board[i + 1][j + 1] == word[done]):
			board[i + 1][j + 1] = ''
			self.solve(i + 1, j + 1, done + 1, length, word, row, col, board, string + word[done])
			board[i + 1][j + 1] = word[done]
		if not self.found and i + 1 < row and (board[i + 1][j] == word[done]):
			board[i + 1][j] = ''
			self.solve(i + 1, j, done + 1, length, word, row, col, board, string + word[done])
			board[i + 1][j] = word[done]
		if not self.found and i + 1 < row and (j - 1 >= 0) and (board[i + 1][j - 1] == word[done]):
			board[i + 1][j - 1] = ''
			self.solve(i + 1, j - 1, done + 1, length, word, row, col, board, string + word[done])
			board[i + 1][j - 1] = word[done]
		if not self.found and j - 1 >= 0 and (board[i][j - 1] == word[done]):
			board[i][j - 1] = ''
			self.solve(i, j - 1, done + 1, length, word, row, col, board, string + word[done])
			board[i][j - 1] = word[done]
		if not self.found and i - 1 >= 0 and (j - 1 >= 0) and (board[i - 1][j - 1] == word[done]):
			board[i - 1][j - 1] = ''
			self.solve(i - 1, j - 1, done + 1, length, word, row, col, board, string + word[done])
			board[i - 1][j - 1] = word[done]
		if not self.found and i - 1 >= 0 and (board[i - 1][j] == word[done]):
			board[i - 1][j] = ''
			self.solve(i - 1, j, done + 1, length, word, row, col, board, string + word[done])
			board[i - 1][j] = word[done]
		if not self.found and i - 1 >= 0 and (j + 1 < col) and (board[i - 1][j + 1] == word[done]):
			board[i - 1][j + 1] = ''
			self.solve(i - 1, j + 1, done + 1, length, word, row, col, board, string + word[done])
			board[i - 1][j + 1] = word[done]

	def wordBoggle(self, board, dictionary):
		self.result = []
		self.found = False
		row = len(board)
		col = len(board[0])
		dictionary = list(set(dictionary))
		for word in dictionary:
			self.found = False
			lst = find_start(word[0], board)
			for x in lst:
				if not self.found:
					(i, j) = (x[0], x[1])
					board[i][j] = ''
					self.solve(i, j, 1, len(word), word, row, col, board, word[0])
					board[i][j] = word[0]
		return self.result


def dfs(mat, i, j, n, m, st, l, k):
	global visited
	global dirn
	if k >= l:
		return True
	if mat[i][j] != st[k]:
		return False
	if k == l - 1:
		return True
	visited[i][j] = True
	res = False
	for d in dirn:
		u = i + d[0]
		v = j + d[1]
		if u >= 0 and v >= 0 and (u < n) and (v < m):
			if visited[u][v] == False:
				res = res or dfs(mat, u, v, n, m, st, l, k + 1)
				if res == True:
					visited[i][j] = False
					return True
	visited[i][j] = False
	return False

def wordBoggleII(mat, words):
	global visited
	global dirn
	n = len(mat)
	m = len(mat[0])
	res = []
	visited = [[False for i in range(m)] for j in range(n)]
	dirn = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)]
	for word in words:
		for i in range(n):
			for j in range(m):
				q = 0
				if dfs(mat, i, j, n, m, word, len(word), 0) and word not in res:
					q = 1
					res.append(word)
					break
			if q == 1:
				break
	return res

class Solution:

	def wordBoggle(self, board, dictionary):
		return wordBoggleII(board, dictionary)


class Solution:

	def search(self, board, word, index, i, j):
		n = len(board)
		m = len(board[0])
		if i < 0 or i > n - 1 or j < 0 or (j > m - 1):
			return False
		if word[index] != board[i][j]:
			return False
		if index == len(word) - 1:
			return True
		ch = board[i][j]
		board[i][j] = '#'
		dx = [-1, 0, +1, -1, +1, -1, 0, +1]
		dy = [+1, +1, +1, 0, 0, -1, -1, -1]
		for x in range(len(dx)):
			if self.search(board, word, index + 1, i + dx[x], j + dy[x]):
				board[i][j] = ch
				return True
		board[i][j] = ch
		return False

	def exist(self, board, word):
		for i in range(len(board)):
			for j in range(len(board[0])):
				if self.search(board, word, 0, i, j):
					return True
		return False

	def wordBoggle(self, board, dictionary):
		wordslist = set()
		for i in range(len(dictionary)):
			if self.exist(board, dictionary[i]):
				wordslist.add(dictionary[i])
		return list(wordslist)


class Solution:

	def dfs(self, board, m, n, word, coords, curind, visited):
		if curind == len(word):
			return True
		visited.add(coords)
		(i, j) = coords
		if i - 1 >= 0 and j - 1 >= 0 and (board[i - 1][j - 1] == word[curind]) and ((i - 1, j - 1) not in visited):
			if self.dfs(board, m, n, word, (i - 1, j - 1), curind + 1, visited):
				return True
		if i - 1 >= 0 and board[i - 1][j] == word[curind] and ((i - 1, j) not in visited):
			if self.dfs(board, m, n, word, (i - 1, j), curind + 1, visited):
				return True
		if i - 1 >= 0 and j + 1 < n and (board[i - 1][j + 1] == word[curind]) and ((i - 1, j + 1) not in visited):
			if self.dfs(board, m, n, word, (i - 1, j + 1), curind + 1, visited):
				return True
		if j - 1 >= 0 and board[i][j - 1] == word[curind] and ((i, j - 1) not in visited):
			if self.dfs(board, m, n, word, (i, j - 1), curind + 1, visited):
				return True
		if j + 1 < n and board[i][j + 1] == word[curind] and ((i, j + 1) not in visited):
			if self.dfs(board, m, n, word, (i, j + 1), curind + 1, visited):
				return True
		if i + 1 < m and j - 1 >= 0 and (board[i + 1][j - 1] == word[curind]) and ((i + 1, j - 1) not in visited):
			if self.dfs(board, m, n, word, (i + 1, j - 1), curind + 1, visited):
				return True
		if i + 1 < m and board[i + 1][j] == word[curind] and ((i + 1, j) not in visited):
			if self.dfs(board, m, n, word, (i + 1, j), curind + 1, visited):
				return True
		if i + 1 < m and j + 1 < n and (board[i + 1][j + 1] == word[curind]) and ((i + 1, j + 1) not in visited):
			if self.dfs(board, m, n, word, (i + 1, j + 1), curind + 1, visited):
				return True
		visited.remove(coords)
		return False

	def wordBoggle(self, board, dictionary):
		startingletters = {}
		m = len(board)
		n = len(board[0])
		out = []
		for i in range(m):
			for j in range(n):
				if board[i][j] not in startingletters:
					startingletters[board[i][j]] = [(i, j)]
				else:
					startingletters[board[i][j]].append((i, j))
		for word in dictionary:
			if word[0] in startingletters:
				for position in startingletters[word[0]]:
					visited = set()
					if self.dfs(board, m, n, word, position, 1, visited):
						out.append(word)
						break
		out = list(set(out))
		out.sort()
		return out


class Solution:

	def dfs(self, board, visited, word, root, r, c):
		if len(word) == 0:
			return True
		(i, j) = root
		visited.add((i, j))
		neighbours = []
		if i > 0:
			neighbours.append((i - 1, j))
		if j > 0:
			neighbours.append((i, j - 1))
		if i > 0 and j > 0:
			neighbours.append((i - 1, j - 1))
		if i < r - 1:
			neighbours.append((i + 1, j))
		if j < c - 1:
			neighbours.append((i, j + 1))
		if i < r - 1 and j < c - 1:
			neighbours.append((i + 1, j + 1))
		if i < r - 1 and j > 0:
			neighbours.append((i + 1, j - 1))
		if i > 0 and j < c - 1:
			neighbours.append((i - 1, j + 1))
		for neighbour in neighbours:
			(i, j) = neighbour
			if (i, j) not in visited and board[i][j] == word[0]:
				finished = self.dfs(board, visited, word[1:], neighbour, r, c)
				if finished:
					return finished
		visited.remove(root)
		return False

	def wordBoggle(self, board, dictionary):
		starts = {}
		found_words = []
		r = len(board)
		c = len(board[0])
		visited = [[0] * c for _ in range(r)]
		for i in range(r):
			for j in range(c):
				for word in dictionary:
					if word[0] == board[i][j]:
						if word in starts:
							starts[word].append((i, j))
						else:
							starts[word] = [(i, j)]
		for word in starts:
			for start in starts[word]:
				found = self.dfs(board, set([start]), word[1:], start, r, c)
				if found:
					found_words.append(word)
					break
		return sorted(found_words)


class TrieNode:

	def __init__(self):
		self.children = {}
		self.end_of_word = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def add_word(self, word):
		cur = self.root
		for c in word:
			if c not in cur.children:
				cur.children[c] = TrieNode()
			cur = cur.children[c]
		cur.end_of_word = True

class Solution:

	def wordBoggle(self, board, dictionary):
		self.row = len(board)
		self.col = len(board[0])
		self.root = Trie()
		for word in dictionary:
			self.root.add_word(word)
		self.visited = [[0 for col in range(self.col)] for row in range(self.row)]
		self.res = []
		root = self.root.root
		for row in range(self.row):
			for col in range(self.col):
				c = board[row][col]
				if c in root.children:
					self.dfs([row, col], root.children[c], c, board)
		return self.res

	def dfs(self, pos, root, path, board):
		if root.end_of_word and path not in self.res:
			self.res.append(path[:])
		(row, col) = (pos[0], pos[1])
		self.visited[row][col] = 1
		neighbors = [[-1, 0], [1, 0], [0, -1], [0, 1], [1, 1], [-1, -1], [1, -1], [-1, 1]]
		for nbr in neighbors:
			new_row = row + nbr[0]
			new_col = col + nbr[1]
			if new_row in range(self.row) and new_col in range(self.col):
				if self.visited[new_row][new_col] == 0:
					c = board[new_row][new_col]
					if c in root.children:
						self.dfs([new_row, new_col], root.children[c], path + c, board)
		self.visited[row][col] = 0
		return


class TrieNode:

	def __init__(self):
		self.children = {}
		self.end_of_word = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def add_word(self, word):
		cur = self.root
		for c in word:
			if c not in cur.children:
				cur.children[c] = TrieNode()
			cur = cur.children[c]
		cur.end_of_word = True

class Solution:

	def wordBoggle(self, board, words):
		self.row = len(board)
		self.col = len(board[0])
		self.n = len(words)
		self.trie = Trie()
		for i in range(self.n):
			self.trie.add_word(words[i])
		self.visited = [[0 for col in range(self.col)] for row in range(self.row)]
		self.res = set()
		root = self.trie.root
		for row in range(self.row):
			for col in range(self.col):
				c = board[row][col]
				if c in root.children:
					self.dfs([row, col], root.children[c], board, c)
		return list(self.res)

	def dfs(self, pos, root, board, path):
		(row, col) = (pos[0], pos[1])
		self.visited[row][col] = 1
		if root.end_of_word:
			self.res.add(path[:])
		neighbor = [[1, 0], [-1, 0], [0, -1], [0, 1], [-1, -1], [1, 1], [-1, 1], [1, -1]]
		for nbr in neighbor:
			new_row = row + nbr[0]
			new_col = col + nbr[1]
			if new_row in range(self.row) and new_col in range(self.col):
				if self.visited[new_row][new_col] == 0:
					c = board[new_row][new_col]
					if c in root.children:
						self.dfs([new_row, new_col], root.children[c], board, path + c)
		self.visited[row][col] = 0
		return


class Trie:

	def __init__(self):
		self.T = {}

	def add(self, word):
		t = self.T
		for c in word:
			if c not in t:
				t[c] = {}
			t = t[c]
		t['#'] = True

class Solution:

	def wordBoggle(self, board, dictionary):
		t = Trie()
		res = []
		for w in dictionary:
			t.add(w)
		for r in range(len(board)):
			for c in range(len(board[0])):
				if len(res) == len(dictionary):
					return res
				self.dfs(board, t.T, r, c, '', res)
		return res

	def dfs(self, board, t, r, c, s, res):
		if '#' in t and t['#']:
			res.append(s)
			t['#'] = False
		if r < 0 or r > len(board) - 1 or c < 0 or (c > len(board[0]) - 1):
			return
		tmp = board[r][c]
		if tmp not in t:
			return
		board[r][c] = '.'
		nbors = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
		for (dr, dc) in nbors:
			self.dfs(board, t[tmp], r + dr, c + dc, s + tmp, res)
		board[r][c] = tmp
		return


class TrieNode:

	def __init__(self):
		self.children = {}
		self.is_word = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, word):
		cur = self.root
		for letter in word:
			if letter not in cur.children:
				cur.children[letter] = TrieNode()
			cur = cur.children[letter]
		cur.is_word = True

	def exists(self, word):
		cur = self.root
		for letter in word:
			if letter not in cur.children:
				return False
			cur = cur.children[letter]
		return cur.is_word

class Solution:

	def wordBoggle(self, board, words):
		USED = '#'
		wordTrie = Trie()
		for word in words:
			wordTrie.insert(word)
		result = set()

		def backtrack(node, prefix, i, j):
			if node.is_word:
				result.add(prefix)
			for (di, dj) in ((0, 1), (0, -1), (-1, 0), (1, 0), (-1, -1), (1, 1), (-1, 1), (1, -1)):
				(ni, nj) = (i + di, j + dj)
				if 0 <= ni < len(board) and 0 <= nj < len(board[0]) and (board[ni][nj] in node.children):
					tmp = board[ni][nj]
					board[ni][nj] = USED
					backtrack(node.children[tmp], prefix + tmp, ni, nj)
					board[ni][nj] = tmp
		for i in range(len(board)):
			for j in range(len(board[i])):
				if board[i][j] in wordTrie.root.children:
					tmp = board[i][j]
					board[i][j] = USED
					backtrack(wordTrie.root.children[tmp], tmp, i, j)
					board[i][j] = tmp
		return list(result)


class Solution:

	def wordBoggle(self, board, dictionary):
		self.R = len(board)
		self.C = len(board[0])
		self.board = board
		res = set()
		for word in dictionary:
			visited = [[False for _ in range(self.C)] for _ in range(self.R)]
			found = False
			for i in range(self.R):
				for j in range(self.C):
					if self.board[i][j] == word[0]:
						if self.dfs(word[1:], i, j, visited):
							res.add(word)
							found = True
							break
				if found:
					break
		return list(res)

	def dfs(self, word, i, j, visited):
		if not word:
			return True
		visited[i][j] = True
		direction = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
		for d in direction:
			if self.isValid(i + d[0], j + d[1], word[0], visited):
				if self.dfs(word[1:], i + d[0], j + d[1], visited):
					return True
		visited[i][j] = False
		return False

	def isValid(self, i, j, ch, visited):
		return i >= 0 and j >= 0 and (i < self.R) and (j < self.C) and (not visited[i][j]) and (ch == self.board[i][j])


class Solution:

	def wordBoggle(self, board, dictionary):
		res = []
		for word in set(dictionary):
			found = False
			for r in range(len(board)):
				if found:
					break
				for c in range(len(board[r])):
					if has_word(board, r, c, word, 0):
						found = True
						break
			if found:
				res.append(word)
		return res

def has_word(board, r, c, word, i):
	if i == len(word):
		return True
	if r < 0 or c < 0 or r == len(board) or (c == len(board[r])):
		return False
	if board[r][c] != word[i]:
		return False
	temp = board[r][c]
	board[r][c] = ''
	has_result = False
	for (nr, nc) in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1), (r + 1, c + 1), (r + 1, c - 1), (r - 1, c + 1), (r - 1, c - 1)]:
		if has_word(board, nr, nc, word, i + 1):
			has_result = True
			break
	board[r][c] = temp
	return has_result


class Solution:

	def wordBoggle(self, board, dictionary):
		(m, n) = (len(board), len(board[0]))
		trie = {}
		stop = '#'
		for word in dictionary:
			node = trie
			for ch in word:
				if ch not in node:
					node[ch] = {}
				node = node[ch]
			node[stop] = True

		def dfs(node, i, j, path):
			if stop in node:
				node.pop(stop, None)
				res.append(path)
			(temp, board[i][j]) = (board[i][j], '$')
			for (nx, ny) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1), (i + 1, j + 1), (i - 1, j - 1), (i + 1, j - 1), (i - 1, j + 1)]:
				if 0 <= nx < m and 0 <= ny < n and (board[nx][ny] in node):
					dfs(node[board[nx][ny]], nx, ny, path + board[nx][ny])
			board[i][j] = temp
		res = []
		for i in range(m):
			for j in range(n):
				if board[i][j] in trie:
					node = trie
					dfs(node[board[i][j]], i, j, board[i][j])
		return res