-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathmax_traversal_within_n_time.py
More file actions
88 lines (77 loc) · 2.21 KB
/
Copy pathmax_traversal_within_n_time.py
File metadata and controls
88 lines (77 loc) · 2.21 KB
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#!/bin/python3
#
# Complete the 'reachTheEnd' function below.
#
# The function is expected to return a STRING.
# The function accepts following parameters:
# 1. STRING_ARRAY grid
# 2. INTEGER maxTime
#
def reachTheEnd(grid, maxTime):
n = len(grid)
# base validations - n vs maxTime
if maxTime < n:
return 'No'
visited = [[0 for _ in range(n)] for _ in range(n)]
return traverse_helper(grid, maxTime, visited, 0, 0, 0, n)
def traverse_helper(grid, maxTime, visited, x, y, cur_time, n):
"""
explore each option
select the current option
validate the constraint
if satisfied
return 'Yes'
unselect the current option
return 'No'
"""
# validate the constraints
print(x, y)
if x == n - 1 and y == n - 1:
if cur_time <= maxTime:
return 'Yes'
else:
return 'No'
# if x < 0 or y < 0 or x >= n or y >= n:
# return
if visited[x][y] == 0:
visited[x][y] = 1
# explore each option
# top
if y - 1 > 0 and y - 1 <= n - 1:
traverse_helper(grid, maxTime, visited, x, y - 1, cur_time + 1, n)
visited[x][y - 1] = 0
# left
if x - 1 > 0 and x - 1 <= n - 1:
traverse_helper(grid, maxTime, visited, x - 1, y, cur_time + 1, n)
visited[x - 1][y] = 0
# right
if x + 1 > 0 and x + 1 <= n - 1:
traverse_helper(grid, maxTime, visited, x + 1, y, cur_time + 1, n)
visited[x + 1][y] = 0
# bottom
if y + 1 > 0 and y + 1 <= n - 1:
traverse_helper(grid, maxTime, visited, x, y + 1, cur_time + 1, n)
visited[x][y + 1] = 0
# return 'No'
if __name__ == '__main__':
# fptr = open(os.environ['OUTPUT_PATH'], 'w')
#
# grid_count = int(input().strip())
#
# grid = []
#
# for _ in range(grid_count):
# grid_item = input()
# grid.append(grid_item)
#
# maxTime = int(input().strip())
#
# result = reachTheEnd(grid, maxTime)
#
# fptr.write(result + '\n')
#
# fptr.close()
grid = [['.', '.'],
['.', '.']]
maxTime = 3
print(reachTheEnd(grid, maxTime))