Given a 2D grid of n*m of characters and a word, find all occurrences of given word in grid. A word can be matched in all 8 directions at any point. Word is said to be found in a direction if all characters match in this direction (not in zig-zag form). The 8 directions are, horizontally left, horizontally right, vertically up, vertically down, and 4 diagonal directions.
Note: The returning list should be lexicographically smallest. If the word can be found in multiple directions starting from the same coordinates, the list should contain the coordinates only once. 
 
Example 1:
Input: grid = {{a,b,c},{d,r,f},{g,h,i}},
word = "abc"
Output: {{0,0}}
Explanation: From (0,0) one can find "abc"
in horizontally right direction.
Example 2:
Input: grid = {{a,b,a,b},{a,b,e,b},{e,b,e,b}}
,word = "abe"
Output: {{0,0},{0,2},{1,0}}
Explanation: From (0,0) one can find "abe" in 
right-down diagonal. From (0,2) one can
find "abe" in left-down diagonal. From
(1,0) one can find "abe" in Horizontally right 
direction.
 
Your Task:
You don't need to read or print anything, Your task is to complete the function searchWord() which takes grid and word as input parameters and returns a list containing the positions from where the word originates in any direction. If there is no such position then returns an empty list.
 
Expected Time Complexity: O(n*m*k) where k is constant
Expected Space Complexity: O(1)
 
Constraints:
1 <= n <= m <= 100
1 <= |word| <= 10

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Graph traversal

Complete search

Starter code: #User function Template for python3



class Solution:

	def searchWord(self, grid, word):

		# Code here

Solutions:
class Solution:

	def searchWord(self, grid, word):
		(n, m, l, x) = (len(grid), len(grid[0]), len(word), [])

		def helper(i, j, k, n, m, l, di, dj):
			if k == l:
				return True
			if j < 0 or i < 0 or j >= m or (i >= n) or (grid[i][j] != word[k]):
				return False
			return helper(i + di, j + dj, k + 1, n, m, l, di, dj)
		moves = [[0, 1], [1, 0], [0, -1], [-1, 0], [1, 1], [1, -1], [-1, -1], [-1, 1]]
		for i in range(n):
			for j in range(m):
				for (di, dj) in moves:
					if grid[i][j] == word[0]:
						if helper(i, j, 0, n, m, l, di, dj):
							x.append([i, j])
							break
		return x


class Solution:

	def searchWord(self, grid, word):
		m = len(grid)
		n = len(grid[0])
		indexes = [[0 for j in range(n)] for i in range(m)]
		d = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
		for i in range(0, m):
			for j in range(0, n):
				if grid[i][j] == word[0]:
					for k in range(0, len(d)):
						ans = self.find(grid, word, m, n, i, j, 0, d[k][0], d[k][1])
						if ans is True:
							indexes[i][j] = 1
		final = []
		for i in range(0, m):
			for j in range(0, n):
				if indexes[i][j] == 1:
					final.append([i, j])
		return final

	def find(self, grid, word, m, n, i, j, index, add_i, add_j):
		if index == len(word):
			return True
		if i < 0 or i >= m or j < 0 or (j >= n):
			return False
		if grid[i][j] != word[index]:
			return False
		new_i = i + add_i
		new_j = j + add_j
		ans = self.find(grid, word, m, n, new_i, new_j, index + 1, add_i, add_j)
		return ans


class Solution:

	def searchWord(self, grid, word):
		ans = []
		n = len(grid)
		m = len(grid[0])

		def find(i, j, k, dr, word, grid):
			if k == len(word):
				return True
			if i < 0 or i >= len(grid) or j < 0 or (j >= len(grid[0])) or (grid[i][j] != word[k]):
				return False
			if dr == 0 and grid[i][j] == word[k]:
				return find(i, j + 1, k + 1, 0, word, grid)
			elif dr == 1 and grid[i][j] == word[k]:
				return find(i, j - 1, k + 1, 1, word, grid)
			elif dr == 2 and grid[i][j] == word[k]:
				return find(i + 1, j, k + 1, 2, word, grid)
			elif dr == 3 and grid[i][j] == word[k]:
				return find(i - 1, j, k + 1, 3, word, grid)
			elif dr == 4 and grid[i][j] == word[k]:
				return find(i + 1, j + 1, k + 1, 4, word, grid)
			elif dr == 5 and grid[i][j] == word[k]:
				return find(i + 1, j - 1, k + 1, 5, word, grid)
			elif dr == 6 and grid[i][j] == word[k]:
				return find(i - 1, j + 1, k + 1, 6, word, grid)
			elif dr == 7 and grid[i][j] == word[k]:
				return find(i - 1, j - 1, k + 1, 7, word, grid)
			return False
		for i in range(n):
			for j in range(m):
				if grid[i][j] == word[0]:
					if find(i, j + 1, 1, 0, word, grid):
						ans.append([i, j])
					elif find(i, j - 1, 1, 1, word, grid):
						ans.append([i, j])
					elif find(i + 1, j, 1, 2, word, grid):
						ans.append([i, j])
					elif find(i - 1, j, 1, 3, word, grid):
						ans.append([i, j])
					elif find(i + 1, j + 1, 1, 4, word, grid):
						ans.append([i, j])
					elif find(i + 1, j - 1, 1, 5, word, grid):
						ans.append([i, j])
					elif find(i - 1, j + 1, 1, 6, word, grid):
						ans.append([i, j])
					elif find(i - 1, j - 1, 1, 7, word, grid):
						ans.append([i, j])
		return ans


class Solution:

	def __compare_direction_substring(self, i, j, k, offset_row, offset_col, n, grid, word):
		while k < n:
			if grid[i][j] != word[k]:
				return False
			i += offset_row
			j += offset_col
			k += 1
		return True

	def searchWord(self, grid, word):
		(r, c, n) = (len(grid), len(grid[0]), len(word))
		offsets = ((0, 1), (0, -1), (1, 0), (-1, 0), (-1, 1), (-1, -1), (1, -1), (1, 1))
		idx_within_range = lambda idx, start, end: start <= idx < end
		res = []
		for i in range(r):
			for j in range(c):
				if grid[i][j] == word[0]:
					for (offset_row, offset_col) in offsets:
						(end_pos_row, end_pos_col) = (i + (n - 1) * offset_row, j + (n - 1) * offset_col)
						if idx_within_range(end_pos_row, 0, r) and idx_within_range(end_pos_col, 0, c):
							if self.__compare_direction_substring(i + offset_row, j + offset_col, 1, offset_row, offset_col, n, grid, word):
								res.append([i, j])
								break
		return res


class Solution:

	def solve(self, i, j, grid, word, x, temp):
		if x == len(word):
			return True
		if (temp == 'top' or temp == 'first') and i + 1 < len(grid) and (grid[i + 1][j] == word[x]):
			if self.solve(i + 1, j, grid, word, x + 1, 'top'):
				return True
		if (temp == 'bottom' or temp == 'first') and i - 1 >= 0 and (grid[i - 1][j] == word[x]):
			if self.solve(i - 1, j, grid, word, x + 1, 'bottom'):
				return True
		if (temp == 'left' or temp == 'first') and j - 1 >= 0 and (grid[i][j - 1] == word[x]):
			if self.solve(i, j - 1, grid, word, x + 1, 'left'):
				return True
		if (temp == 'right' or temp == 'first') and j + 1 < len(grid[0]) and (grid[i][j + 1] == word[x]):
			if self.solve(i, j + 1, grid, word, x + 1, 'right'):
				return True
		if (temp == 'topleft' or temp == 'first') and i - 1 >= 0 and (j - 1 >= 0) and (grid[i - 1][j - 1] == word[x]):
			if self.solve(i - 1, j - 1, grid, word, x + 1, 'topleft'):
				return True
		if (temp == 'bottomright' or temp == 'first') and i + 1 < len(grid) and (j + 1 < len(grid[0])) and (grid[i + 1][j + 1] == word[x]):
			if self.solve(i + 1, j + 1, grid, word, x + 1, 'bottomright'):
				return True
		if (temp == 'bottomleft' or temp == 'first') and i + 1 < len(grid) and (j - 1 >= 0) and (grid[i + 1][j - 1] == word[x]):
			if self.solve(i + 1, j - 1, grid, word, x + 1, 'bottomleft'):
				return True
		if (temp == 'topright' or temp == 'first') and i - 1 >= 0 and (j + 1 < len(grid[0])) and (grid[i - 1][j + 1] == word[x]):
			if self.solve(i - 1, j + 1, grid, word, x + 1, 'topright'):
				return True
		return False

	def searchWord(self, grid, word):
		res = []
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == word[0]:
					if self.solve(i, j, grid, word, 1, 'first'):
						res.append((i, j))
		return res


class Solution:

	def __init__(self):
		self.R = None
		self.C = None
		self.dir = [[-1, 0], [1, 0], [1, 1], [1, -1], [-1, -1], [-1, 1], [0, 1], [0, -1]]

	def search2D(self, grid, row, col, word):
		if grid[row][col] != word[0]:
			return False
		for (x, y) in self.dir:
			(rd, cd) = (row + x, col + y)
			flag = True
			for k in range(1, len(word)):
				if 0 <= rd < self.R and 0 <= cd < self.C and (word[k] == grid[rd][cd]):
					rd += x
					cd += y
				else:
					flag = False
					break
			if flag:
				return True
		return False

	def searchWord(self, grid, word):
		self.R = len(grid)
		self.C = len(grid[0])
		f = []
		for row in range(self.R):
			for col in range(self.C):
				if self.search2D(grid, row, col, word):
					f.append((row, col))
		return sorted(set(f))


class Solution:

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

	def searchWord(self, grid, word):
		ans = []
		n = len(grid)
		m = len(grid[0])
		dirs = [(-1, 0), (0, -1), (-1, -1), (-1, 1), (1, -1), (1, 0), (1, 1), (0, 1)]

		def is_possible(grid, word, i, j, dirs):
			n = len(grid)
			m = len(grid[0])
			for dir in dirs:
				newi = i
				newj = j
				c = 0
				while 0 <= newi < n and 0 <= newj < m and (c < len(word)) and (grid[newi][newj] == word[c]):
					newi += dir[0]
					newj += dir[1]
					c += 1
				if c == len(word):
					return True
			return False
		for i in range(n):
			for j in range(m):
				if grid[i][j] == word[0] and is_possible(grid, word, i, j, dirs):
					ans.append([i, j])
		return ans


class Solution:

	def searchWord(self, board, word):

		def help(board, w, r, c):
			x = [[-1, 0], [1, 0], [-1, 0], [0, 1], [0, -1], [-1, -1], [-1, 1], [1, -1], [1, 1]]
			if board[r][c] != w[0]:
				return False
			for i in x:
				rs = r + i[0]
				cs = c + i[1]
				Flag = True
				for k in range(1, len(w)):
					if 0 <= rs < len(board) and 0 <= cs < len(board[0]) and (w[k] == board[rs][cs]):
						rs += i[0]
						cs += i[1]
					else:
						Flag = False
						break
				if Flag:
					return True
			return False
		l = []
		rows = len(board)
		cols = len(board[0])
		for i in range(rows):
			for j in range(cols):
				if help(board, word, i, j):
					l.append([i, j])
		l.sort(key=lambda x: x[0])
		return l


class Solution:

	def searchWord(self, grid, word):
		res = []
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == word[0]:
					if self.find(i, j, grid, word, 1, 'any'):
						res.append((i, j))
		return res

	def find(self, i, j, grid, word, x, dir):
		if x == len(word):
			return True
		if (dir == 'top' or dir == 'any') and i + 1 < len(grid) and (grid[i + 1][j] == word[x]):
			if self.find(i + 1, j, grid, word, x + 1, 'top'):
				return True
		if (dir == 'bottom' or dir == 'any') and i - 1 >= 0 and (grid[i - 1][j] == word[x]):
			if self.find(i - 1, j, grid, word, x + 1, 'bottom'):
				return True
		if (dir == 'left' or dir == 'any') and j - 1 >= 0 and (grid[i][j - 1] == word[x]):
			if self.find(i, j - 1, grid, word, x + 1, 'left'):
				return True
		if (dir == 'right' or dir == 'any') and j + 1 < len(grid[0]) and (grid[i][j + 1] == word[x]):
			if self.find(i, j + 1, grid, word, x + 1, 'right'):
				return True
		if (dir == 'topleft' or dir == 'any') and i - 1 >= 0 and (j - 1 >= 0) and (grid[i - 1][j - 1] == word[x]):
			if self.find(i - 1, j - 1, grid, word, x + 1, 'topleft'):
				return True
		if (dir == 'bottomright' or dir == 'any') and i + 1 < len(grid) and (j + 1 < len(grid[0])) and (grid[i + 1][j + 1] == word[x]):
			if self.find(i + 1, j + 1, grid, word, x + 1, 'bottomright'):
				return True
		if (dir == 'bottomleft' or dir == 'any') and i + 1 < len(grid) and (j - 1 >= 0) and (grid[i + 1][j - 1] == word[x]):
			if self.find(i + 1, j - 1, grid, word, x + 1, 'bottomleft'):
				return True
		if (dir == 'topright' or dir == 'any') and i - 1 >= 0 and (j + 1 < len(grid[0])) and (grid[i - 1][j + 1] == word[x]):
			if self.find(i - 1, j + 1, grid, word, x + 1, 'topright'):
				return True
		return False


class Solution:

	def searchWord(self, grid, word):

		def _lps(w):
			(lps, j) = ([0] * L, 0)
			for i in range(1, L):
				while j >= 0 and w[i] != w[j]:
					j = lps[j - 1] if j > 0 else -1
				j += 1
				lps[i] = j
			return lps

		def _match(gen):
			j = 0
			for (i, c) in enumerate(gen):
				if c == word[j]:
					j += 1
					if j == L:
						yield (i - L + 1)
						j = lps[L - 1]
				else:
					while j >= 0 and c != word[j]:
						j = lps[j - 1] if j > 0 else -1
					j += 1
		import numpy as np
		L = len(word)
		lps = _lps(word)
		G = np.array(grid)
		(R, C) = G.shape
		ok = [[False] * C for _ in range(R)]
		if C >= L:
			for r in range(R):
				for c in _match(G[r]):
					ok[r][c] = True
				for c in _match(reversed(G[r])):
					ok[r][C - 1 - c] = True
		if R >= L:
			for c in range(C):
				for io in _match(G[:, c]):
					ok[io][c] = True
				for io in _match(reversed(G[:, c])):
					ok[R - 1 - io][c] = True
		for off in range(-(R - 1), C):
			if off < 0:
				(sr, sc) = (-off, 0)
			else:
				(sr, sc) = (0, off)
			s = G.diagonal(off)
			ls = len(s)
			for io in _match(s):
				ok[sr + io][sc + io] = True
			for io in _match(reversed(s)):
				ok[sr + ls - 1 - io][sc + ls - 1 - io] = True
		FG = np.fliplr(G)
		for off in range(-(R - 1), C):
			if off < 0:
				(sr, sc) = (-off, 0)
			else:
				(sr, sc) = (0, off)
			s = FG.diagonal(off)
			ls = len(s)
			for io in _match(s):
				ok[sr + io][C - 1 - sc - io] = True
			for io in _match(reversed(s)):
				ok[sr + ls - 1 - io][C - sc - ls + io] = True
		ans = [(r, c) for r in range(R) for c in range(C) if ok[r][c]]
		return ans


class Solution:

	def helper(self, idx, dir, i, j, grid, word):
		if not (0 <= i and i < len(grid) and (0 <= j) and (j < len(grid[0]))):
			return False
		if word[idx] != grid[i][j]:
			return False
		if idx == len(word) - 1:
			return True
		if dir == 0:
			return self.helper(idx + 1, 1, i, j + 1, grid, word) or self.helper(idx + 1, 2, i - 1, j + 1, grid, word) or self.helper(idx + 1, 3, i - 1, j, grid, word) or self.helper(idx + 1, 4, i - 1, j - 1, grid, word) or self.helper(idx + 1, 5, i, j - 1, grid, word) or self.helper(idx + 1, 6, i + 1, j - 1, grid, word) or self.helper(idx + 1, 7, i + 1, j, grid, word) or self.helper(idx + 1, 8, i + 1, j + 1, grid, word)
		elif dir == 1:
			return self.helper(idx + 1, 1, i, j + 1, grid, word)
		elif dir == 2:
			return self.helper(idx + 1, 2, i - 1, j + 1, grid, word)
		elif dir == 3:
			return self.helper(idx + 1, 3, i - 1, j, grid, word)
		elif dir == 4:
			return self.helper(idx + 1, 4, i - 1, j - 1, grid, word)
		elif dir == 5:
			return self.helper(idx + 1, 5, i, j - 1, grid, word)
		elif dir == 6:
			return self.helper(idx + 1, 6, i + 1, j - 1, grid, word)
		elif dir == 7:
			return self.helper(idx + 1, 7, i + 1, j, grid, word)
		elif dir == 8:
			return self.helper(idx + 1, 8, i + 1, j + 1, grid, word)

	def searchWord(self, grid, word):
		n = len(grid)
		m = len(grid[0])
		Ans = []
		for i in range(n):
			for j in range(m):
				if self.helper(0, 0, i, j, grid, word):
					Ans.append([i, j])
		return Ans


class Solution:

	def solve(self, i, j, k, n, m, l, dx, dy, grid, visited, word):
		if visited[i][j]:
			return False
		visited[i][j] = 1
		(x, y) = (dx + i, dy + j)
		if x >= 0 and x < n and (y >= 0) and (y < m):
			if k + 1 == l - 1 and word[k + 1] == grid[x][y]:
				return True
			elif k + 1 < l and word[k + 1] == grid[x][y]:
				if self.solve(x, y, k + 1, n, m, l, dx, dy, grid, visited, word):
					return True
		return False

	def searchWord(self, grid, word):
		(n, m, l) = (len(grid), len(grid[0]), len(word))
		res = []
		dx = [0, 0, 1, -1, 1, 1, -1, -1]
		dy = [1, -1, 0, 0, -1, 1, -1, 1]
		for i in range(n):
			for j in range(m):
				if grid[i][j] == word[0]:
					if l == 1 and [i, j] not in res:
						res.append([i, j])
						continue
					for ind in range(8):
						visited = [[0] * m for i in range(n)]
						if self.solve(i, j, 0, n, m, l, dx[ind], dy[ind], grid, visited, word) and [i, j] not in res:
							res.append([i, j])
		res.sort()
		return res


class Solution:

	def helper(self, word, moves, i, j, grid):
		if grid[i][j] != word[0]:
			return False
		for (a, b) in moves:
			(new_i, new_j) = (i + a, j + b)
			st = True
			for k in range(1, len(word)):
				if 0 <= new_i < len(grid) and 0 <= new_j < len(grid[0]) and (grid[new_i][new_j] == word[k]):
					new_i += a
					new_j += b
				else:
					st = False
					break
			if st:
				return True
		return False

	def searchWord(self, grid, word):
		moves = [[0, 1], [1, 0], [0, -1], [-1, 0], [1, 1], [1, -1], [-1, -1], [-1, 1]]
		res = []
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if self.helper(word, moves, i, j, grid) == True:
					res.append([i, j])
		return res


class Solution:

	def searchWord(self, grid, word):
		(n, m, l, x) = (len(grid), len(grid[0]), len(word), [])

		def right(i, j, k, n, m, l):
			if k == l:
				return True
			if j >= m or grid[i][j] != word[k]:
				return False
			return right(i, j + 1, k + 1, n, m, l)

		def left(i, j, k, n, m, l):
			if k == l:
				return True
			if j < 0 or grid[i][j] != word[k]:
				return False
			return left(i, j - 1, k + 1, n, m, l)

		def up(i, j, k, n, m, l):
			if k == l:
				return True
			if i < 0 or grid[i][j] != word[k]:
				return False
			return up(i - 1, j, k + 1, n, m, l)

		def down(i, j, k, n, m, l):
			if k == l:
				return True
			if i >= n or grid[i][j] != word[k]:
				return False
			return down(i + 1, j, k + 1, n, m, l)

		def upleft(i, j, k, n, m, l):
			if k == l:
				return True
			if i < 0 or j < 0 or grid[i][j] != word[k]:
				return False
			return upleft(i - 1, j - 1, k + 1, n, m, l)

		def upright(i, j, k, n, m, l):
			if k == l:
				return True
			if i < 0 or j >= m or grid[i][j] != word[k]:
				return False
			return upright(i - 1, j + 1, k + 1, n, m, l)

		def downright(i, j, k, n, m, l):
			if k == l:
				return True
			if i >= n or j >= m or grid[i][j] != word[k]:
				return False
			return downright(i + 1, j + 1, k + 1, n, m, l)

		def downleft(i, j, k, n, m, l):
			if k == l:
				return True
			if i >= n or j < 0 or grid[i][j] != word[k]:
				return False
			return downleft(i + 1, j - 1, k + 1, n, m, l)
		for i in range(n):
			for j in range(m):
				if grid[i][j] == word[0]:
					if right(i, j, 0, n, m, l) == True:
						x.append([i, j])
						continue
					if left(i, j, 0, n, m, l) == True:
						x.append([i, j])
						continue
					if up(i, j, 0, n, m, l) == True:
						x.append([i, j])
						continue
					if down(i, j, 0, n, m, l) == True:
						x.append([i, j])
						continue
					if upleft(i, j, 0, n, m, l):
						x.append([i, j])
						continue
					if upright(i, j, 0, n, m, l):
						x.append([i, j])
						continue
					if downright(i, j, 0, n, m, l):
						x.append([i, j])
						continue
					elif downleft(i, j, 0, n, m, l):
						x.append([i, j])
						continue
		return x


class Solution:

	def __init__(self):
		self.ans = []

	def dfs(self, grid, i, j, n, m, curr_word, word, start_i, start_j, dir):
		if curr_word == len(word):
			if (start_i, start_j) not in self.ans:
				self.ans.append((start_i, start_j))
			return True
		if i >= n or i < 0 or j >= m or (j < 0) or (grid[i][j] != word[curr_word]):
			return
		temp = grid[i][j]
		grid[i][j] = '#'
		if dir == 'V':
			self.dfs(grid, i + 1, j, n, m, curr_word + 1, word, start_i, start_j, dir)
			self.dfs(grid, i - 1, j, n, m, curr_word + 1, word, start_i, start_j, dir)
		if dir == 'H':
			self.dfs(grid, i, j + 1, n, m, curr_word + 1, word, start_i, start_j, dir)
			self.dfs(grid, i, j - 1, n, m, curr_word + 1, word, start_i, start_j, dir)
		if dir == 'DR':
			self.dfs(grid, i + 1, j + 1, n, m, curr_word + 1, word, start_i, start_j, dir)
			self.dfs(grid, i - 1, j - 1, n, m, curr_word + 1, word, start_i, start_j, dir)
		if dir == 'DL':
			self.dfs(grid, i + 1, j - 1, n, m, curr_word + 1, word, start_i, start_j, dir)
			self.dfs(grid, i - 1, j + 1, n, m, curr_word + 1, word, start_i, start_j, dir)
		grid[i][j] = temp

	def searchWord(self, grid, word):
		try:
			n = len(grid)
			m = len(grid[0])
			for i in range(n):
				for j in range(m):
					if grid[i][j] == word[0]:
						self.dfs(grid, i, j, n, m, 0, word, i, j, 'H')
						self.dfs(grid, i, j, n, m, 0, word, i, j, 'V')
						self.dfs(grid, i, j, n, m, 0, word, i, j, 'DR')
						self.dfs(grid, i, j, n, m, 0, word, i, j, 'DL')
			return self.ans
		except Exception as e:
			print('e', e)


class Solution:

	def searchWord(self, grid, word):
		n = len(grid)
		m = len(grid[0])
		l = len(word)
		output = []
		for i in range(n):
			for j in range(m):
				if i >= l - 1:
					candi = ''
					for k in range(l):
						candi += grid[i - k][j]
					if candi == word:
						output.append((i, j))
				if i + l <= n:
					candi = ''
					for k in range(l):
						candi += grid[i + k][j]
					if candi == word:
						output.append((i, j))
				if j >= l - 1:
					candi = ''
					for k in range(l):
						candi += grid[i][j - k]
					if candi == word:
						output.append((i, j))
				if j + l <= m:
					candi = ''
					for k in range(l):
						candi += grid[i][j + k]
					if candi == word:
						output.append((i, j))
				if i >= l - 1 and j >= l - 1:
					candi = ''
					for k in range(l):
						candi += grid[i - k][j - k]
					if candi == word:
						output.append((i, j))
				if i >= l - 1 and j + l <= m:
					candi = ''
					for k in range(l):
						candi += grid[i - k][j + k]
					if candi == word:
						output.append((i, j))
				if i + l <= n and j >= l - 1:
					candi = ''
					for k in range(l):
						candi += grid[i + k][j - k]
					if candi == word:
						output.append((i, j))
				if i + l <= n and j + l <= m:
					candi = ''
					for k in range(l):
						candi += grid[i + k][j + k]
					if candi == word:
						output.append((i, j))
		return sorted(set(output))


class Solution:

	def findWord(self, mat, target, dir, i, j, curind):
		if i < 0 or j < 0 or i >= len(mat) or (j >= len(mat[0])):
			return 0
		curchar = mat[i][j]
		if target[curind] != curchar:
			return 0
		if curind == len(target) - 1:
			return 1
		count = 0
		if dir == 0:
			return self.findWord(mat, target, 1, i, j + 1, curind + 1) or self.findWord(mat, target, 2, i - 1, j + 1, curind + 1) or self.findWord(mat, target, 3, i - 1, j, curind + 1) or self.findWord(mat, target, 4, i - 1, j - 1, curind + 1) or self.findWord(mat, target, 5, i, j - 1, curind + 1) or self.findWord(mat, target, 6, i + 1, j - 1, curind + 1) or self.findWord(mat, target, 7, i + 1, j, curind + 1) or self.findWord(mat, target, 8, i + 1, j + 1, curind + 1)
		elif dir == 1:
			return self.findWord(mat, target, 1, i, j + 1, curind + 1)
		elif dir == 2:
			return self.findWord(mat, target, 2, i - 1, j + 1, curind + 1)
		elif dir == 3:
			return self.findWord(mat, target, 3, i - 1, j, curind + 1)
		elif dir == 4:
			return self.findWord(mat, target, 4, i - 1, j - 1, curind + 1)
		elif dir == 5:
			return self.findWord(mat, target, 5, i, j - 1, curind + 1)
		elif dir == 6:
			return self.findWord(mat, target, 6, i + 1, j - 1, curind + 1)
		elif dir == 7:
			return self.findWord(mat, target, 7, i + 1, j, curind + 1)
		elif dir == 8:
			return self.findWord(mat, target, 8, i + 1, j + 1, curind + 1)
		return count

	def searchWord(self, grid, word):
		ans = []
		for i in range(0, len(grid)):
			for j in range(0, len(grid[0])):
				if self.findWord(grid, word, 0, i, j, 0):
					ans.append([i, j])
		return ans


class Solution:

	def searchWord(self, grid, word):

		def count(row, col):
			if grid[row][col] != word[0]:
				return False
			for (x, y) in rcmat:
				rd = row + x
				cl = col + y
				flag = True
				for k in range(1, len(word)):
					if -1 < rd < R and -1 < cl < C and (grid[rd][cl] == word[k]):
						rd = rd + x
						cl = cl + y
					else:
						flag = False
						break
				if flag:
					return True
			return False
		ls = []
		rcmat = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, 0], [1, 1], [1, -1]]
		R = len(grid)
		C = len(grid[0])
		for i in range(R):
			for j in range(C):
				if count(i, j):
					ls.append([i, j])
		return ls


class Solution:

	def searchWord(self, grid, word):
		directions = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
		if not grid or not word:
			return []
		n = len(grid)
		m = len(grid[0])
		res = []

		def dfs(i, j):
			if word[0] != grid[i][j]:
				return False
			for dir in directions:
				newx = i + dir[0]
				newy = j + dir[1]
				flag = True
				for k in range(1, len(word)):
					if newx < n and newx >= 0 and (newy < m) and (newy >= 0) and (word[k] == grid[newx][newy]):
						newx += dir[0]
						newy += dir[1]
					else:
						flag = False
						break
				if flag:
					return True
			return False
		for i in range(n):
			for j in range(m):
				if dfs(i, j):
					res.append([i, j])
		return res


def search2D(grid, row, col, word):
	di = [[-1, 0], [1, 0], [1, 1], [1, -1], [-1, -1], [-1, 1], [0, 1], [0, -1]]
	if grid[row][col] != word[0]:
		return False
	R = len(grid)
	C = len(grid[0])
	for (x, y) in di:
		(rd, cd) = (row + x, col + y)
		flag = True
		for k in range(1, len(word)):
			if 0 <= rd < R and 0 <= cd < C and (word[k] == grid[rd][cd]):
				rd += x
				cd += y
			else:
				flag = False
				break
		if flag:
			return True
	return False

def patternSearch(grid, word):
	res = []
	R = len(grid)
	C = len(grid[0])
	for row in range(R):
		for col in range(C):
			if search2D(grid, row, col, word):
				res.append((row, col))
	return res

class Solution:

	def searchWord(self, grid, word):
		return patternSearch(grid, word)


class Solution:

	def search(self, i, j, grid, word, n, m):
		if grid[i][j] != word[0]:
			return False
		drc = [[-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1]]
		for xy in drc:
			x = xy[0]
			y = xy[1]
			f = True
			r = i + x
			c = j + y
			for k in range(1, len(word)):
				if 0 <= r < n and 0 <= c < m and (grid[r][c] == word[k]):
					r += x
					c += y
				else:
					f = False
					break
			if f:
				return True

	def searchWord(self, grid, word):
		n = len(grid)
		m = len(grid[0])
		res = []
		for i in range(n):
			for j in range(m):
				if self.search(i, j, grid, word, n, m):
					res.append([i, j])
		return res


class Solution:

	def searchWord(self, grid, word):

		def possible(word, grid, i, j, d):
			row = [0, 1, 0, -1, 1, 1, -1, -1]
			col = [1, 0, -1, 0, 1, -1, -1, 1]
			if d == 0:
				right = len(grid[0]) - j - 1 >= len(word) - 1
				if not right:
					return
			if d == 1:
				down = len(grid) - i - 1 >= len(word) - 1
				if not down:
					return
			if d == 2:
				left = j >= len(word) - 1
				if not left:
					return
			if d == 3:
				up = i >= len(word) - 1
				if not up:
					return
			if d == 4:
				right = len(grid[0]) - j - 1 >= len(word) - 1
				down = len(grid) - i - 1 >= len(word) - 1
				if not right or not down:
					return
			if d == 5:
				left = j >= len(word) - 1
				down = len(grid) - i - 1 >= len(word) - 1
				if not left or not down:
					return
			if d == 6:
				up = i >= len(word) - 1
				left = j >= len(word) - 1
				if not left or not up:
					return
			if d == 7:
				up = i >= len(word) - 1
				right = len(grid[0]) - j - 1 >= len(word) - 1
				if not right or not up:
					return
			h = 1
			a = row[d] + i
			b = col[d] + j
			while True:
				if word[h] == grid[a][b]:
					if h == len(word) - 1:
						return True
					h += 1
					a += row[d]
					b += col[d]
				else:
					return
		result = []
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if word[0] == grid[i][j]:
					if len(word) == 1:
						result.append([i, j])
						continue
					for k in range(8):
						if possible(word, grid, i, j, k):
							result.append([i, j])
							break
		return result


def search(grid, word, row, col):
	y = [0, -1, -1, -1, 0, 1, 1, 1]
	x = [1, 1, 0, -1, -1, -1, 0, 1]
	for i in range(8):
		X = x[i] + row
		Y = y[i] + col
		k = 1
		while X >= 0 and X < len(grid) and (Y >= 0) and (Y < len(grid[0])) and (k < len(word)) and (grid[X][Y] == word[k]):
			X += x[i]
			Y += y[i]
			k += 1
		if k == len(word):
			return True
		else:
			continue
	return False

class Solution:

	def searchWord(self, grid, word):
		row = len(grid)
		col = len(grid[0])
		ans = []
		for i in range(row):
			for j in range(col):
				if grid[i][j] == word[0]:
					if search(grid, word, i, j):
						move = (i, j)
						ans.append(move)
		return ans


class Solution:

	def searchWord(self, grid, word):

		def helper(i, j, k, n, m, l, x, y):
			if k == l:
				return True
			if i < 0 or j < 0 or j >= m or (i >= n) or (grid[i][j] != word[k]):
				return False
			return helper(i + x, j + y, k + 1, n, m, l, x, y)
		(n, m) = (len(grid), len(grid[0]))
		l = len(word)
		res = []
		direction = [[0, 1], [1, 0], [0, -1], [-1, 0], [1, 1], [1, -1], [-1, -1], [-1, 1]]
		for i in range(n):
			for j in range(m):
				for (x, y) in direction:
					if grid[i][j] == word[0]:
						if helper(i, j, 0, n, m, l, x, y):
							res.append([i, j])
							break
		return res


class Solution:

	def searchWord(self, grid, word):
		ans = set()
		dir = [[-1, -1], [-1, 1], [1, -1], [1, 1], [-1, 0], [0, -1], [0, 1], [1, 0]]

		def dfs(i, j, ind, d):
			if ind == len(word):
				return True
			if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])):
				return False
			if grid[i][j] != word[ind]:
				return False
			return dfs(i + dir[d][0], j + dir[d][1], ind + 1, d)
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == word[0]:
					for k in range(8):
						if dfs(i, j, 0, k):
							ans.add((i, j))
		return sorted(list(ans))


class Solution:

	def searchWord(self, grid, word):
		ans = []
		r = len(grid)
		c = len(grid[0])

		def recurs(c, starti, startj, direct, i, j, ans):
			if c == '':
				if [starti, startj] not in ans:
					ans.append([starti, startj])
				return
			elif i < 0 or i == len(grid) or j < 0 or (j == len(grid[0])):
				return
			elif grid[i][j] == c[0]:
				a = c[1:]
				if not direct:
					recurs(a, i, j, 'L', i, j - 1, ans)
					recurs(a, i, j, 'R', i, j + 1, ans)
					recurs(a, i, j, 'U', i - 1, j, ans)
					recurs(a, i, j, 'D', i + 1, j, ans)
					recurs(a, i, j, 'UR', i - 1, j + 1, ans)
					recurs(a, i, j, 'UL', i - 1, j - 1, ans)
					recurs(a, i, j, 'DL', i + 1, j - 1, ans)
					recurs(a, i, j, 'DR', i + 1, j + 1, ans)
				elif direct == 'L':
					recurs(a, starti, startj, 'L', i, j - 1, ans)
				elif direct == 'R':
					recurs(a, starti, startj, 'R', i, j + 1, ans)
				elif direct == 'U':
					recurs(a, starti, startj, 'U', i - 1, j, ans)
				elif direct == 'D':
					recurs(a, starti, startj, 'D', i + 1, j, ans)
				elif direct == 'UR':
					recurs(a, starti, startj, 'UR', i - 1, j + 1, ans)
				elif direct == 'UL':
					recurs(a, starti, startj, 'UL', i - 1, j - 1, ans)
				elif direct == 'DL':
					recurs(a, starti, startj, 'DL', i + 1, j - 1, ans)
				else:
					recurs(a, starti, startj, 'DR', i + 1, j + 1, ans)
			else:
				return
		for i in range(r):
			for j in range(c):
				recurs(word, None, None, None, i, j, ans)
		return ans


class Solution:

	def isValid(self, x, y, n, m):
		if x >= 0 and y >= 0 and (x < n) and (y < m):
			return True
		return False

	def solve(self, mat, word, i, j, n, m, X, Y):
		for x in range(8):
			nx = i + X[x]
			ny = j + Y[x]
			flag = True
			for w in range(1, len(word)):
				if self.isValid(nx, ny, n, m) and mat[nx][ny] == word[w]:
					nx += X[x]
					ny += Y[x]
				else:
					flag = False
			if flag:
				return True
		return False

	def searchWord(self, mat, word):
		n = len(mat)
		m = len(mat[0])
		X = [0, 0, 1, -1, -1, -1, 1, 1]
		Y = [1, -1, 0, 0, -1, 1, 1, -1]
		ans = []
		for i in range(n):
			for j in range(m):
				if mat[i][j] == word[0]:
					if self.solve(mat, word, i, j, n, m, X, Y):
						ans.append([i, j])
		return ans


class Solution:

	def searchWord(self, grid, word):
		row = len(grid)
		col = len(grid[0])
		directory = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
		output = []
		for i in range(row):
			for j in range(col):
				if self.findString(grid, word, i, j, row, col, directory):
					output.append([i, j])
		return output

	def findString(self, grid, word, row, col, row_max, col_max, directory):
		if grid[row][col] != word[0]:
			return False
		for (x, y) in directory:
			rd = row + x
			cd = col + y
			flag = True
			for k in range(1, len(word)):
				if 0 <= rd < row_max and 0 <= cd < col_max and (word[k] == grid[rd][cd]):
					rd = rd + x
					cd = cd + y
				else:
					flag = False
					break
			if flag:
				return True
		return False


class Solution:

	def check(self, grid, word, n, m, n_word, i, j):
		y = i
		x = j
		index = 0
		while y >= 0 and grid[y][x] == word[index]:
			y -= 1
			index += 1
			if index == n_word:
				return True
		y = i
		x = j
		index = 0
		while y >= 0 and x < m and (grid[y][x] == word[index]):
			y -= 1
			x += 1
			index += 1
			if index == n_word:
				return True
		y = i
		x = j
		index = 0
		while x < m and grid[y][x] == word[index]:
			x += 1
			index += 1
			if index == n_word:
				return True
		y = i
		x = j
		index = 0
		while y < n and x < m and (grid[y][x] == word[index]):
			y += 1
			x += 1
			index += 1
			if index == n_word:
				return True
		y = i
		x = j
		index = 0
		while y < n and grid[y][x] == word[index]:
			y += 1
			index += 1
			if index == n_word:
				return True
		y = i
		x = j
		index = 0
		while y < n and x >= 0 and (grid[y][x] == word[index]):
			y += 1
			x -= 1
			index += 1
			if index == n_word:
				return True
		y = i
		x = j
		index = 0
		while x >= 0 and grid[y][x] == word[index]:
			x -= 1
			index += 1
			if index == n_word:
				return True
		y = i
		x = j
		index = 0
		while y >= 0 and x >= 0 and (grid[y][x] == word[index]):
			y -= 1
			x -= 1
			index += 1
			if index == n_word:
				return True
		return False

	def searchWord(self, grid, word):
		n = len(grid)
		m = len(grid[0])
		n_word = len(word)
		ans = []
		for i in range(n):
			for j in range(m):
				if self.check(grid, word, n, m, n_word, i, j):
					ans.append([i, j])
		return ans


class Solution:

	def searchWord(self, grid, word):

		def dfs(i, r, c, move):
			if r < 0 or r >= len(grid) or c < 0 or (c >= len(grid[0])) or (word[i] != grid[r][c]):
				return False
			if i == len(word) - 1 and word[i] == grid[r][c]:
				return True
			if move == '':
				return dfs(i + 1, r - 1, c, 't') or dfs(i + 1, r - 1, c + 1, 'tr') or dfs(i + 1, r, c + 1, 'r') or dfs(i + 1, r + 1, c + 1, 'br') or dfs(i + 1, r + 1, c, 'b') or dfs(i + 1, r + 1, c - 1, 'bl') or dfs(i + 1, r, c - 1, 'l') or dfs(i + 1, r - 1, c - 1, 'tl')
			elif move == 't':
				return dfs(i + 1, r - 1, c, 't')
			elif move == 'tr':
				return dfs(i + 1, r - 1, c + 1, 'tr')
			elif move == 'r':
				return dfs(i + 1, r, c + 1, 'r')
			elif move == 'br':
				return dfs(i + 1, r + 1, c + 1, 'br')
			elif move == 'b':
				return dfs(i + 1, r + 1, c, 'b')
			elif move == 'bl':
				return dfs(i + 1, r + 1, c - 1, 'bl')
			elif move == 'l':
				return dfs(i + 1, r, c - 1, 'l')
			else:
				return dfs(i + 1, r - 1, c - 1, 'tl')
		res = []
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if dfs(0, i, j, ''):
					res.append([i, j])
		return res


class Solution:

	def searchWord(self, M, w):
		(R, C) = (len(M), len(M[0]))
		ans = []
		for r in range(R):
			for c in range(C):
				if M[r][c] == w[0] and expand(r, c, R, C, M, w):
					ans.append([r, c])
		return ans

def expand(sr, sc, R, C, M, w):
	for dr in range(-1, 2):
		for dc in range(-1, 2):
			if dr == 0 and dc == 0:
				continue
			(r, c) = (sr, sc)
			i = 0
			while 0 <= r < R and 0 <= c < C and (i < len(w)) and (M[r][c] == w[i]):
				i += 1
				(r, c) = (r + dr, c + dc)
			if i == len(w):
				return True
	return False


class Solution:

	def perf(self, grid, word, i, j, n, m):
		move = [[-1, 0], [-1, -1], [0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1]]
		for k in range(8):
			x = i + move[k][0]
			y = j + move[k][1]
			idx = 1
			for p in range(1, len(word)):
				if x < 0 or x >= n or y < 0 or (y >= m) or (grid[x][y] != word[p]):
					break
				x = x + move[k][0]
				y = y + move[k][1]
				idx += 1
			if idx == len(word):
				return True
		return False

	def searchWord(self, grid, word):
		n = len(grid)
		m = len(grid[0])
		res = []
		for i in range(n):
			for j in range(m):
				if grid[i][j] == word[0]:
					if self.perf(grid, word, i, j, n, m):
						res.append([i, j])
		return res


class Solution:

	def searchWord(self, grid, word):

		def dfs(r, c, ind, d):
			if r >= row or c >= col or r < 0 or (c < 0) or (grid[r][c] != word[ind]):
				return False
			if ind == len(word) - 1:
				return True
			return dfs(r + d[0], c + d[1], ind + 1, d)
		row = len(grid)
		col = len(grid[0])
		dir = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (1, -1), (-1, -1)]
		ans = []
		for r in range(row):
			for c in range(col):
				if grid[r][c] == word[0]:
					for d in dir:
						if dfs(r, c, 0, d):
							ans.append([r, c])
							break
		return ans


class Solution:

	def searchWord(self, grid, word):
		r = len(grid)
		c = len(grid[0])
		res = []
		l = len(word)
		for i in range(len(grid)):
			for j in range(len(grid[i])):
				if grid[i][j] == word[0]:
					h_r = grid[i][j:j + l]
					h_r_w = ''.join(h_r)
					if j - l + 1 >= 0:
						h_l = grid[i][j - l + 1:j + 1][::-1]
						h_l_w = ''.join(h_l)
					else:
						h_l_w = ''
					v_d = [x[j] for x in grid][i:i + l]
					v_d_w = ''.join(v_d)
					if i - l + 1 >= 0:
						v_u = [x[j] for x in grid][i - l + 1:i + 1][::-1]
						v_u_w = ''.join(v_u)
					else:
						v_u_w = ''
					if i + l - 1 < r and j + l - 1 < c:
						d1_d = [grid[i + x][j + x] for x in range(0, l)]
						d1_d_w = ''.join(d1_d)
					else:
						d1_d_w = ''
					if i - l + 1 >= 0 and j - l + 1 >= 0:
						d1_u = [grid[i - x][j - x] for x in range(0, l)]
						d1_u_w = ''.join(d1_u)
					else:
						d1_u_w = ''
					if i + l - 1 < r and j - l + 1 >= 0:
						d2_d = [grid[i + x][j - x] for x in range(0, l)]
						d2_d_w = ''.join(d2_d)
					else:
						d2_d_w = ''
					if i - l + 1 >= 0 and j + l - 1 < c:
						d2_u = [grid[i - x][j + x] for x in range(0, l)]
						d2_u_w = ''.join(d2_u)
					else:
						d2_u_w = ''
					if h_r_w == word:
						res.append([i, j])
					elif h_l_w == word:
						res.append([i, j])
					elif v_d_w == word:
						res.append([i, j])
					elif v_u_w == word:
						res.append([i, j])
					elif d1_d_w == word:
						res.append([i, j])
					elif d1_u_w == word:
						res.append([i, j])
					elif d2_d_w == word:
						res.append([i, j])
					elif d2_u_w == word:
						res.append([i, j])
		return res


class Solution:

	def rec(self, i, j, grid, m, n, word, l, vis):
		paths = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
		for kk in paths:
			k = 0
			(ii, jj) = (i, j)
			while 0 <= ii < m and 0 <= jj < n:
				if k == l:
					return True
				if grid[ii][jj] != word[k]:
					break
				(ii, jj) = (ii + kk[0], jj + kk[1])
				k += 1
			if k == l:
				return True
		return False

	def searchWord(self, grid, word):
		(m, n) = (len(grid), len(grid[0]))
		ans = []
		l = len(word)
		for i in range(m):
			for j in range(n):
				vis = [[0] * n for i in range(m)]
				if self.rec(i, j, grid, m, n, word, l, vis):
					ans.append([i, j])
		return ans


def dfs(row, col, word, m, n, grid, direction):
	if len(word) == 0:
		return True
	(x, y) = direction
	if row + x >= 0 and row + x < m and (col + y >= 0) and (col + y < n) and (grid[row + x][col + y] == word[0]):
		if dfs(row + x, col + y, word[1:], m, n, grid, direction):
			return True
	return False

class Solution:

	def searchWord(self, grid, word):
		m = len(grid)
		n = len(grid[0])
		result = []
		directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
		for i in range(m):
			for j in range(n):
				if grid[i][j] == word[0]:
					for direction in directions:
						if dfs(i, j, word[1:], m, n, grid, direction):
							result.append((i, j))
							break
		return result


class Solution:

	def searchWord(self, grid, word):
		dx = [1, 1, 0, -1, -1, -1, 0, 1]
		dy = [0, 1, 1, 1, 0, -1, -1, -1]
		res = []
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				for k in range(8):
					x = i
					y = j
					flag = True
					for l in range(len(word)):
						if x >= len(grid) or x < 0 or y >= len(grid[0]) or (y < 0) or (grid[x][y] != word[l]):
							flag = False
							break
						else:
							x += dx[k]
							y += dy[k]
					if flag:
						res.append([i, j])
						break
		return res


class Solution:

	def searchWord(self, grid, word):
		n = len(grid)
		m = len(grid[0])

		def dfs(i, j, k, ind):
			if ind == len(word):
				return True
			if i < 0 or j < 0 or i >= n or (j >= m) or (grid[i][j] != word[ind]):
				return False
			return dfs(i + k[0], j + k[1], k, ind + 1)
		d = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (1, -1), (-1, -1)]
		ans = []
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == word[0]:
					for k in d:
						if dfs(i, j, k, 0):
							ans.append([i, j])
							break
		return ans


class Solution:

	def search(self, grid, row, col, word, r, c, dirc):
		if grid[row][col] != word[0]:
			return False
		for (x, y) in dirc:
			rd = row + x
			cd = col + y
			flag = True
			for k in range(1, len(word)):
				if 0 <= rd < r and 0 <= cd < c and (word[k] == grid[rd][cd]):
					rd += x
					cd += y
				else:
					flag = False
					break
			if flag:
				return True
		return False

	def searchWord(self, grid, word):
		r = len(grid)
		c = len(grid[0])
		dirc = [[-1, 0], [1, 0], [1, 1], [1, -1], [-1, -1], [-1, 1], [0, 1], [0, -1]]
		res = []
		for row in range(r):
			for col in range(c):
				if self.search(grid, row, col, word, r, c, dirc):
					res.append([row, col])
		res.sort()
		return res


class Solution:

	def find(self, p, q, grid, word, r, n, m):
		di = [[0, -1], [0, 1], [-1, 0], [-1, -1], [-1, 1], [1, 0], [1, -1], [1, 1]]
		for i in range(8):
			c = 0
			h = p
			h1 = q
			while h < n and h1 < m and (h >= 0) and (h1 >= 0) and (c < r) and (word[c] == grid[h][h1]):
				c += 1
				h += di[i][0]
				h1 += di[i][1]
			if c == r:
				return True
		return False

	def searchWord(self, grid, word):
		n = len(grid)
		m = len(grid[0])
		l = []
		for i in range(n):
			for j in range(m):
				if grid[i][j] == word[0]:
					if self.find(i, j, grid, word, len(word), n, m):
						l.append([i, j])
		return l


class Solution:

	def searchWord(self, grid, word):
		result = []
		for i in range(0, len(grid)):
			for j in range(0, len(grid[0])):
				if grid[i][j] == word[0] and self.dfs(i, j, 0, word, grid, 0):
					result.append([i, j])
		return result

	def dfs(self, i, j, count, word, grid, prevdir):
		if len(word) == count:
			return True
		if i >= 0 and j >= 0 and (i < len(grid)) and (j < len(grid[0])) and (grid[i][j] == word[count]):
			temp = grid[i][j]
			grid[i][j] = 0
			if prevdir == 0:
				if self.dfs(i + 1, j, count + 1, word, grid, 1) or self.dfs(i - 1, j, count + 1, word, grid, 2) or self.dfs(i, j + 1, count + 1, word, grid, 3) or self.dfs(i, j - 1, count + 1, word, grid, 4) or self.dfs(i + 1, j + 1, count + 1, word, grid, 5) or self.dfs(i - 1, j - 1, count + 1, word, grid, 6) or self.dfs(i - 1, j + 1, count + 1, word, grid, 7) or self.dfs(i + 1, j - 1, count + 1, word, grid, 8):
					grid[i][j] = temp
					return True
			if prevdir == 1 and self.dfs(i + 1, j, count + 1, word, grid, 1) or (prevdir == 2 and self.dfs(i - 1, j, count + 1, word, grid, 2)) or (prevdir == 3 and self.dfs(i, j + 1, count + 1, word, grid, 3)) or (prevdir == 4 and self.dfs(i, j - 1, count + 1, word, grid, 4)) or (prevdir == 5 and self.dfs(i + 1, j + 1, count + 1, word, grid, 5)) or (prevdir == 6 and self.dfs(i - 1, j - 1, count + 1, word, grid, 6)) or (prevdir == 7 and self.dfs(i - 1, j + 1, count + 1, word, grid, 7)) or (prevdir == 8 and self.dfs(i + 1, j - 1, count + 1, word, grid, 8)):
				grid[i][j] = temp
				return True
			grid[i][j] = temp
		return False


class Solution:

	def internal_search(self, word, grid, R, C, row, col):
		if grid[row][col] != word[0]:
			return False
		dxy = [[0, 1], [0, -1], [-1, 0], [1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]]
		for (dx, dy) in dxy:
			new_row = row + dx
			new_col = col + dy
			flag = True
			for i in range(1, len(word)):
				if new_row >= 0 and new_row < R and (new_col >= 0) and (new_col < C) and (grid[new_row][new_col] == word[i]):
					new_row += dx
					new_col += dy
				else:
					flag = False
					break
			if flag:
				return True
		return False

	def searchWord(self, grid, word):
		R = len(grid)
		C = len(grid[0])
		res = []
		for row in range(R):
			for col in range(C):
				if self.internal_search(word, grid, R, C, row, col):
					res.append([row, col])
		return res


class Solution:

	def internal_search(self, idx, word, grid, row, col, row_max, col_max):
		if row < 0 or row > row_max or col < 0 or (col > col_max):
			return False
		if grid[row][col] != word[0]:
			return False
		dxy = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]]
		for (dx, dy) in dxy:
			new_row = row + dx
			new_col = col + dy
			found = True
			for i in range(1, len(word)):
				if new_row >= 0 and new_row <= row_max and (new_col >= 0) and (new_col <= col_max) and (word[i] == grid[new_row][new_col]):
					new_row += dx
					new_col += dy
				else:
					found = False
					break
			if found:
				return True
		return False

	def searchWord(self, grid, word):
		row_count = len(grid)
		col_count = len(grid[0])
		res = []
		for row in range(row_count):
			for col in range(col_count):
				if self.internal_search(0, word, grid, row, col, row_count - 1, col_count - 1):
					res.append([row, col])
		return res


direction = [[-1, 0], [1, 0], [1, 1], [1, -1], [-1, -1], [-1, 1], [0, 1], [0, -1]]

class Solution:

	def searchWord(self, grid, word):
		ans = []
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if self.findword(grid, i, j, word):
					ans.append((i, j))
		return ans

	def findword(self, grid, row, col, word):
		if grid[row][col] != word[0]:
			return False
		for (x, y) in direction:
			(rd, cd) = (row + x, col + y)
			flag = True
			for k in range(1, len(word)):
				if rd in range(len(grid)) and cd in range(len(grid[0])) and (word[k] == grid[rd][cd]):
					rd += x
					cd += y
				else:
					flag = False
					break
			if flag:
				return True
		return False


class Solution:

	def searchWord(self, grid, word):
		n = len(grid)
		m = len(grid[0])
		d = [[-1, 0], [1, 0], [1, 1], [1, -1], [-1, -1], [-1, 1], [0, 1], [0, -1]]

		def solve(grid, row, col, w, n, m):
			if w[0] != grid[row][col]:
				return False
			for di in d:
				r = row + di[0]
				c = col + di[1]
				flag = True
				for j in range(1, len(w)):
					if r >= 0 and r < n and (c >= 0) and (c < m) and (w[j] == grid[r][c]):
						r += di[0]
						c += di[1]
					else:
						flag = False
						break
				if flag:
					return True
			return False
		ans = []
		for i in range(n):
			for j in range(m):
				if solve(grid, i, j, word, n, m):
					ans.append([i, j])
		return ans


class Solution:

	def searchWord(self, grid, word):

		def fun(i, j, k, s, f, l1, m1, n1):
			if i < n and j < m and (i >= 0) and (j >= 0) and (s + grid[i][j] == word):
				return 1
			if i < 0 or j < 0 or i >= n or (j >= m):
				return
			ans = 0
			if f == 0 and grid[i][j] == word[k]:
				ans = fun(i - 1, j, k + 1, s + grid[i][j], 0, l1, m1, n1)
				f += 1
				(i, j, k) = (l1, m1, n1)
				s = ''
				if ans == 1:
					return 1
			if f == 1 and grid[i][j] == word[k]:
				ans = fun(i + 1, j, k + 1, s + grid[i][j], 1, l1, m1, n1)
				f += 1
				(i, j, k) = (l1, m1, n1)
				s = ''
				if ans == 1:
					return 1
			if f == 2 and grid[i][j] == word[k]:
				ans = fun(i, j + 1, k + 1, s + grid[i][j], 2, l1, m1, n1)
				f += 1
				(i, j, k) = (l1, m1, n1)
				s = ''
				if ans == 1:
					return 1
			if f == 3 and grid[i][j] == word[k]:
				ans = fun(i, j - 1, k + 1, s + grid[i][j], 3, l1, m1, n1)
				f += 1
				(i, j, k) = (l1, m1, n1)
				s = ''
				if ans == 1:
					return 1
			if f == 4 and grid[i][j] == word[k]:
				ans = fun(i - 1, j + 1, k + 1, s + grid[i][j], 4, l1, m1, n1)
				f += 1
				(i, j, k) = (l1, m1, n1)
				s = ''
				if ans == 1:
					return 1
			if f == 5 and grid[i][j] == word[k]:
				ans = fun(i - 1, j - 1, k + 1, s + grid[i][j], 5, l1, m1, n1)
				f += 1
				(i, j, k) = (l1, m1, n1)
				s = ''
				if ans == 1:
					return 1
			if f == 6 and grid[i][j] == word[k]:
				ans = fun(i + 1, j - 1, k + 1, s + grid[i][j], 6, l1, m1, n1)
				f += 1
				(i, j, k) = (l1, m1, n1)
				s = ''
				if ans == 1:
					return 1
			if f == 7 and grid[i][j] == word[k]:
				ans = fun(i + 1, j + 1, k + 1, s + grid[i][j], 7, l1, m1, n1)
				f += 1
				(i, j, k) = (l1, m1, n1)
				s = ''
				if ans == 1:
					return 1
			return ans
		res = []
		for i in range(0, n):
			for j in range(0, m):
				if grid[i][j] == word[0]:
					if len(word) == 1:
						res.append([i, j])
					else:
						ans = fun(i, j, 0, '', 0, i, j, 0)
						if ans == 1:
							res.append([i, j])
		return res


class Solution:

	def searchWord(self, grid, word):

		def check(i, j, x, y, ll, n, grid, word, r, c):
			if i < 0 or i >= r or j < 0 or (j >= c):
				return False
			if ll == n - 1:
				if word[ll] == grid[i][j]:
					return True
				return False
			if word[ll] == grid[i][j]:
				return check(i + x, j + y, x, y, ll + 1, n, grid, word, r, c)
			return False
		r = len(grid)
		c = len(grid[0])
		n = len(word)
		ans = []
		step = [[1, 1], [-1, -1], [1, -1], [-1, 1], [1, 0], [-1, 0], [0, 1], [0, -1]]
		for i in range(r):
			for j in range(c):
				if grid[i][j] == word[0]:
					for (x, y) in step:
						if check(i, j, x, y, 0, n, grid, word, r, c):
							ans += [[i, j]]
							break
		return ans


class Solution:

	def solve(self, i, j, m, n, grid, word):
		if grid[i][j] != word[0]:
			return False
		temp = [[1, 0], [0, 1], [-1, 0], [0, -1], [-1, 1], [1, -1], [1, 1], [-1, -1]]
		r = i
		c = j
		for k in temp:
			flag = True
			i = r
			j = c
			i = i + k[0]
			j = j + k[1]
			for q in range(1, len(word)):
				if i >= 0 and i < m and (j >= 0) and (j < n) and (grid[i][j] == word[q]):
					i = i + k[0]
					j = j + k[1]
				else:
					flag = False
					break
			if flag:
				return True
		return False

	def searchWord(self, grid, word):
		ans = []
		m = len(grid)
		n = len(grid[0])
		for i in range(m):
			for j in range(n):
				if self.solve(i, j, m, n, grid, word):
					ans.append((i, j))
		return ans


class Solution:

	def searchWord(self, grid, word):

		def found(i, j, d):
			wl = len(word)
			for k in range(wl):
				if grid[i][j] != word[k]:
					return False
				else:
					(i, j) = (i + d[0], j + d[1])
					if i < 0 or i >= n or j < 0 or (j >= m):
						return False if k < wl - 1 else True
			return True
		directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]
		r = []
		(n, m) = (len(grid), len(grid[0]))
		for i in range(n):
			for j in range(m):
				for d in directions:
					if found(i, j, d):
						r.append([i, j])
						break
		return r


class Solution:

	def searchWord(self, grid, word):

		def valid(i, j):
			if 0 <= i < len(grid) and 0 <= j < len(grid[0]):
				return True
			return False
		x = [0, 0, -1, -1, -1, 1, 1, 1]
		y = [-1, 1, -1, 0, 1, -1, 0, 1]

		def soln(i, j, dirn, m):
			if m == len(word):
				return True
			if dirn == -1:
				for d in range(8):
					tx = i + x[d]
					ty = j + y[d]
					if valid(tx, ty) and grid[tx][ty] == word[m]:
						if soln(tx, ty, d, m + 1):
							return True
				return False
			else:
				tx = i + x[dirn]
				ty = j + y[dirn]
				if valid(tx, ty) and grid[tx][ty] == word[m]:
					if soln(tx, ty, dirn, m + 1):
						return True
				return False
		soln.res = []
		for r in range(len(grid)):
			for c in range(len(grid[0])):
				if grid[r][c] == word[0]:
					if soln(r, c, -1, 1):
						soln.res.append((r, c))
		return soln.res


class Solution:

	def solve(self, i, j, grid, word, idx, dirx, diry):
		if idx == len(word):
			return True
		else:
			found = False
			if 0 <= i + dirx < len(grid) and 0 <= j + diry < len(grid[0]) and (grid[i + dirx][j + diry] == word[idx]):
				found |= self.solve(i + dirx, j + diry, grid, word, idx + 1, dirx, diry)
			return found

	def searchWord(self, grid, word):
		dx = [1, -1, 0, 0, 1, 1, -1, -1]
		dy = [0, 0, 1, -1, 1, -1, 1, -1]
		r = len(grid)
		c = len(grid[0])
		ans = []
		for i in range(r):
			for j in range(c):
				if grid[i][j] == word[0]:
					found = False
					if len(word) == 1:
						found = True
					else:
						found = False
						for k in range(8):
							if 0 <= i + dx[k] < len(grid) and 0 <= j + dy[k] < len(grid[0]) and (grid[i + dx[k]][j + dy[k]] == word[1]):
								found |= self.solve(i + dx[k], j + dy[k], grid, word, 2, dx[k], dy[k])
					if found:
						ans.append((i, j))
		return ans