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.
Link
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:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#!/usr/bin/pyfrom collections import defaultdictdef 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 Falseif __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!" |
