Grid Matching

# Grid search
# Given a grid of alphabets find all possible paths to construct a word
# Move horizontally, vertically and diagonally to any coordinate with a distance 1
# Path should be a set of unique coordinates

'''
S T A R
A R Y T
N T S O
U P N O

Word: Start

Output: count of possible paths
6
'''
def isSafe(r,c,grid):
    maxR = len(grid)
    maxC = len(grid[0])
    if r>=0 and c>=0 and r<maxR and c<maxC:
        return True
    return False

def getNgbrs(r,c,grid):
    stepR = [-1,-1,-1,0,1,1, 1, 0]
    stepC = [-1, 0, 1,1,1,0,-1,-1]
    i=0
    ngbrs = []
    while i<len(stepR):
        curR = r+stepR[i]
        curC = c+stepC[i]
        if isSafe(curR,curC,grid):
            ngbrs.append((curR,curC))
        i+=1
    return ngbrs

def search(grid,word,r,c):
    toTrav = [(r,c)]
    visited = {}
    visited[(r,c)] = "queue"
    i=0
    count = 0
    indList = []
    while len(toTrav)>0 and i<len(word):
        cur = toTrav[-1]
        if visited[cur] == "word":
            i -= 1
            visited[cur] = "seen"
            toTrav.pop()
            indList.pop()
            continue
        curR,curC = cur[0],cur[1]
        if word[i]==grid[curR][curC]:
            visited[cur] = "word"
            indList.append(cur)
            if i == len(word)-1:
                count += 1
                toTrav.pop()
                print indList
                indList.pop()
                visited[cur] = "seen"
            else:
                ngbrs = getNgbrs(curR,curC,grid)
                for ngbr in ngbrs:
                    if ngbr not in visited or visited[ngbr] != "word":
                        toTrav.append(ngbr)
                        visited[ngbr] = "queue"
                i += 1
        else:
            toTrav.pop()
            visited[cur] = "seen"
    return count


def gridSearch(word, grid):
    rootChar = word[0]
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == rootChar:
                #start search
                count += search(grid,word,r,c)
    return count

grid = [['s','t','a','r'],
        ['a','r','y','t'],
        ['n','t','s','o'],
        ['u','p','n','o']]
print gridSearch("start",grid)