You are viewing a single comment's thread. Return to all comments →
Python 3 Build graph representation and then use Dijkstra
def grid_to_graph(grid): n = len(grid) nnodes = n**2 neighbors = {} for row in range(n): found_dot, pos = False, 0 while pos <= n: if not found_dot: if pos < n: if grid[row][pos] == '.': found_dot = True first_dot = pos else: if (pos == n) or (grid[row][pos] == 'X'): for j in range(first_dot, pos-1): for k in range(j+1, pos): try: neighbors[(row*n)+j].append((row*n)+k) except KeyError: neighbors[(row*n)+j] = [(row*n)+k] try: neighbors[(row*n)+k].append((row*n)+j) except KeyError: neighbors[(row*n)+k] = [(row*n)+j] found_dot = False del first_dot pos += 1 for col in range(n): found_dot, pos = False, 0 while pos <= n: if not found_dot: if pos < n: if grid[pos][col] == '.': found_dot = True first_dot = pos else: if (pos == n) or (grid[pos][col] == 'X'): for j in range(first_dot, pos-1): for k in range(j+1, pos): try: neighbors[(j*n)+col].append((k*n)+col) except KeyError: neighbors[(j*n)+col] = [(k*n)+col] try: neighbors[(k*n)+col].append((j*n)+col) except KeyError: neighbors[(k*n)+col] = [(j*n)+col] found_dot = False del first_dot pos += 1 return nnodes, neighbors def minimumMoves(grid, startX, startY, goalX, goalY): n = len(grid) nnodes, neighbors = grid_to_graph(grid) source, target = (startX*n) + startY, (goalX*n) + goalY dist = [float('inf')]*nnodes dist[source] = 0 Q = {j:None for j in range(nnodes)} while Q: u, u_dist = None, float('inf') for j in Q.keys(): j_dist = dist[j] if j_dist < u_dist: u, u_dist = j, j_dist if u is None: u = j if u == target: break del Q[u] for neighbor in neighbors[u]: try: Q[neighbor] except KeyError: continue alt = dist[u] + 1 if alt < dist[neighbor]: dist[neighbor] = alt return dist[target]
Seems like cookies are disabled on this browser, please enable them to open this website
Castle on the Grid
You are viewing a single comment's thread. Return to all comments →
Python 3 Build graph representation and then use Dijkstra