# Use a depth‑first search (DFS) from every cell that matches the first letter,
# exploring all valid directions until the full word is matched.
def dfs(grid, r, c, word, index, visited):
if index == len(word):
return True
rows = len(grid)
cols = len(grid[0])
if r < 0 or c < 0 or r >= rows or c >= cols:
return False
if visited[r][c]:
return False
if grid[r][c] != word[index]:
return False
visited[r][c] = True
found = (
dfs(grid, r + 1, c, word, index + 1, visited) or
dfs(grid, r - 1, c, word, index + 1, visited) or
dfs(grid, r, c + 1, word, index + 1, visited) or
dfs(grid, r, c - 1, word, index + 1, visited)
)
visited[r][c] = False
return found
def wordExist(grid, word):
rows = len(grid)
cols = len(grid[0])
visited = [[False] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
if dfs(grid, r, c, word, 0, visited):
return True
return False
def main():
grid = [
['a', 'b', 'c', 'e'],
['s', 'f', 'c', 's'],
['a', 'd', 'e', 'e']
]
word = "see"
result = wordExist(grid, word)
print(1 if result else 0)
if __name__ == "__main__":
main()
'''
run:
1
'''
