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{


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}