HRank count luck.py

#!/usr/bin/py
from collections import defaultdict
 
def hermionesWand(arr, K, max_x, max_y):
    # find both entry and exit points
    for idx, line in enumerate(arr):
        for inner_idx in range(len(line)):
            if line[inner_idx] == 'M':
                start = (idx, inner_idx)
            if line[inner_idx] == '*':
                end = (idx, inner_idx)
 
    st = [start]
    tracker = defaultdict(int)
    tracker[start] = 0
 
    # iterate the DFS list
    while st:
        curr = st.pop()
 
        # exit found
        if (curr == end):
            print("number of fork:",tracker[curr])
            return tracker[curr] == K
 
        # save all exits that were not visited before
        inner_st = set()
        if (curr[0] > 0 and (arr[curr[0]-1][curr[1]] == "." or arr[curr[0]-1][curr[1]] == "*")) \
        and (curr[0]-1, curr[1]) not in tracker:
            inner_st.add((curr[0]-1, curr[1]))
        if (curr[1] > 0 and (arr[curr[0]][curr[1]-1] == "." or arr[curr[0]][curr[1]-1] == "*")) \
        and (curr[0], curr[1]-1) not in tracker:
            inner_st.add((curr[0], curr[1]-1))
        if (curr[0] < max_y -1 and (arr[curr[0]+1][curr[1]] == "." or arr[curr[0]+1][curr[1]] == "*")) \
        and (curr[0]+1, curr[1]) not in tracker:
            inner_st.add((curr[0]+1, curr[1]))
        if (curr[1] < max_x -1 and (arr[curr[0]][curr[1]+1] == "." or arr[curr[0]][curr[1]+1] == "*")) \
        and (curr[0], curr[1]+1) not in tracker:
            inner_st.add((curr[0], curr[1]+1))
 
        # a crossroad
        if len(inner_st) > 1:
            tracker[curr] += 1
 
        # save the nodes to DFS list
        for n in inner_st:
            #print(tracker[n])
            tracker[n] = tracker[curr]
            #print(tracker[n])
            #print()
            st.append(n)
 
    return False
 
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        n, m = map(int, input().split())
        a = []
        for line in range(n):
            a.append(list(input()))
        k = int(input())
        if hermionesWand(a, k, m, n):
            print("Impressed")
        else:
            print("Oops!")