# Modern Ludo

BFS

## # Input & Output

@param length: the length of board
@param connections: the connections of the positions
@return: the minimum steps to reach the end

1
2
3

## # Solution

Note:

1. The 6-sided die enables positions 2 to 7 to be reached in 1 step from position 1
2. For each starting point in connections, there might be multiple destinations $\rightarrow$ choose the smallest dist
3. A position can reach from 1 to 10 by two connections: [1, 5] and [5, 10]
4. A node might be revisited and dist might update $\rightarrow$ it's not a traditional BFS requiring a visited set.

Complexity

time: $O(n)$
space: $O(n)$

def modernLudo(self, length, connections):
queue = [1]
dist = {1: 0}
# initialize dist
for d in range(2, length+1):
dist[d] = sys.maxsize

while queue:
for d in range(1, 7):
if npos <= length and dist[npos] > dist[head] + 1:
queue.append(npos)

for k in range(len(connections)):
queue.append(connections[k][1])

return dist[length]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21