We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
KnightL on a Chessboard
KnightL on a Chessboard
+ 4 comments very bad explanation of the sample test case
+ 3 comments BFS works like a charm here because in unweighted graphs BFS guarantees that the first time you visit a cell it gives the shortest path.
+ 1 comment Can somebody explain the problem.For 5X5 chess board how the result is :
4 4 2 8 4 2 4 4 2 4 -1 -1 8 4 -1 1
I did not get anything out of the explanation.
+ 0 comments bad explaination ...
+ 5 comments Python 3 solution.
A couple things to note: - The number of moves funciton is symetteric, so I went ahead and memoized it which will half our run time (don't think this is necessary but a good thing to recognize) - I notice a lot of people are using long if statements to get the adjacent list of positions. I felt a simple filter lambda was cleaner.
memo = [[]] def adj(a, b, x, y, n): return filter(lambda v : v[0] >= 0 and v[1] >= 0 and v[0] < n and v[1] < n, [ [x + a, y + b], [x + a, y - b], [x - a, y + b], [x - a, y - b], [x + b, y + a], [x + b, y - a], [x - b, y + a], [x - b, y - a], ]) def move(a, b, n): global memo # Since move(a, b, n) == move(b, a, n), # we take advantage of this symmtery by memoization. if memo[a][b] is not None: return memo[a][b] visited = [[False] * n for _ in range(n)] # Queue stores elements as [x, y, depth] # Start with top left position queue = [[0, 0, 0]] while len(queue) > 0: x, y, l = queue.pop() # At the end, return level of node if x == n - 1 and y == n - 1: memo[a][b] = l memo[b][a] = l return l neighbors = [ [x_i, y_i] for x_i, y_i in adj(a, b, x, y, n) if visited[y_i][x_i] == False ] for x_i, y_i in neighbors: visited[y_i][x_i] = True queue.insert(0, [x_i, y_i, l + 1]) memo[a][b] = -1 memo[b][a] = -1 return -1 # Complete the knightlOnAChessboard function below. def knightlOnAChessboard(n): global memo memo = [[None for _ in range(n + 1)] for _ in range(n + 1)] results = [] for a in range(1, n): results.append([]) for b in range(1, n): results[a - 1].append(move(a, b, n)) return results
Load more conversations
Sort 109 Discussions, By:
Please Login in order to post a comment