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/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!" |