Source code for tryalgo.dist_grid

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Distances in a grid
jill-jenn vie et christoph durr - 2014-2018
--------------------------------------------
"""

from collections import deque


# snip{
[docs]def dist_grid(grid, source, target=None): """Distances in a grid by BFS :param grid: matrix with 4-neighborhood :param (int,int) source: pair of row, column ind_ices :param (int,int) target: exploration stops if target is reached :complexity: linear in grid size """ rows = len(grid) cols = len(grid[0]) i, j = source grid[i][j] = 's' Q = deque() Q.append(source) while Q: i1, j1 = Q.popleft() for di, dj, symbol in [(0, +1, '>'), (0, -1, '<'), (+1, 0, 'v'), (-1, 0, '^')]: # explore all directions i2 = i1 + di j2 = j1 + dj if not (0 <= i2 < rows and 0 <= j2 < cols): continue # reached the bounds of the grid if grid[i2][j2] != ' ': # inaccessible or already visited continue grid[i2][j2] = symbol # mark visit if (i2, j2) == target: grid[i2][j2] = 't' # goal is reached return Q.append((i2, j2))
# snip}