Answer to Question #345373 in Python for Bhavani

Question

Search Game

A grid of letters may contain a word hidden somewhere within it. The letters of the word may be traced from the starting letter by moving a single letter at a time, up, down, left or right. For example, suppose we are looking for the word BISCUIT in this grid:

0 1 2 3

0 B I T R

1 I U A S

2 S C V W

3 D O N E

The word starts in the top left corner, continues downwards for 2 more letters, then the letter to the right followed by 2 letters moving upwards, the final letter at the right of the penultimate one.

Write a program in which we give target word and a grid of letters as input returns a list of tuples, each tuple being the row and column of the corresponding letter in the grid (numbered from 0). If the word cannot be found, output the string Not present

input1:

after

4

a b c d

f e f g

t e r r

a b i j

Output: [(0, 0),(1, 0),(2, 0),(2, 1),(2, 2)]

input2:

search

4

s e a c

r c c c

h e e e

h e e e

output: Not Present

Answer 1

word = input()
n = int(input())
grid = [input().split() for i in range(n) ]


def getPath(moves, letters, x, y):
    if(letters[0]!=grid[x][y]):
        return []
    moves.append((x,y))


    if(len(letters)==1):
        return moves
    
    if x+1<n and (x+1,y) not in moves:
        result = getPath(moves.copy(), letters[1:], x+1, y)
        if(result):
            return result
    if x-1>=0 and (x-1,y) not in moves:
        result = getPath(moves.copy(), letters[1:], x-1, y)
        if(result):
            return result


    if y+1<n and (x,y+1) not in moves:
        result = getPath(moves.copy(), letters[1:], x, y+1)
        if(result):
            return result


    if y-1>=0 and (x,y-1) not in moves:
        result = getPath(moves.copy(), letters[1:], x+1, y)
        if(result):
            return result
    return []


    
startingPoints = []
for i in range(n):
    for j in range(n):
        if grid[i][j] == word[0]:
            startingPoints.append((i,j))
path = []
for i in range(len(startingPoints)):
    path = getPath([], word, startingPoints[i][0], startingPoints[i][1])
    if path:
        break
if(path):
    print(path)
else:
    print("Not Present")