Short Problem Definition:

Hermione Granger is lost in the Forbidden Forest while collecting some herbs for a magical potion. The forest is magical and has only one exit point, which magically transports her back to the Hogwarts School of Witchcraft and Wizardry.

Count Luck

Complexity:

time complexity is O(n)

space complexity is O(n)

Execution:

I solve this challenge using DFS and dynamic programming. I iterate over all n positions (denoted with .) using DFS. For each node, I remember the number of crossroads Hermione encountered up to that point. DFS does not guarantee to find the optimal solution in terms of path length.

Solution:

#!/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 xrange(len(line)):
            if line[inner_idx] == 'M':
                h = (idx, inner_idx)
            if line[inner_idx] == '*':
                e = (idx, inner_idx)

    st = [h]
    tracker = defaultdict(int)
    tracker[h] = 0

    # iterate the DFS list
    while st:
        curr = st.pop()

        # exit found
        if (curr == e):
            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:
            tracker[n] = tracker[curr]
            st.append(n)

    return False

if __name__ == '__main__':
    t = int(raw_input())
    for _ in xrange(t):
        n, m = map(int, raw_input().split())
        a = []
        for line in xrange(n):
            a.append(list(raw_input()))
        k = int(raw_input())
        if hermionesWand(a, k, m, n):
            print "Impressed"
        else:
            print "Oops!"