CODEWITHSUNDEEP
algorithmloopslanguage-agnosticnested-loops
Megidd
Megidd

Reputation: 7961

Loop over NxN grid cells based of proximity to a certain cell

I have a N by N grid. I have a certain grid cell labeled with 0:

checkered board

I intend to loop over grid cells, starting with 0 cell, in this order:

How can I compose the loop?

I tried to follow this post. But I cannot adapt it to suit my situation.

Upvotes: 1

Views: 398

Answers (2)

Reblochon Masque
Reblochon Masque

Reputation: 36682

You can fill the entire grid using a Breadth First Search: Starting with the cell with value zero, it will expand in concentric waves, adding one to each subsequent layer further away from the center.

Here is an example in Python3

from collections import deque
from typing import List, Tuple


class Grid:
    """represents a grid of cells indexed like a matrix:
    rows first, then columns
    rows, cols, r, c, row, col, cr, cc are ints
    rowcol = tuple of ints
    """    
    eight_offsets = [(1, 1), (1, 0), (1, -1), (0, 1), (0, -1), (-1, 1), (-1, 0), (-1, -1)]

    def __init__(self, rows: int, cols: int):
        self.rows = rows
        self.cols = cols
        self.cells = [[None for col in range(cols)] for row in range(rows)]

    def fill_grid_BFS(self, rowcol: Tuple[int, int]) -> None:
        """fills each cell with its distance from the cell at rowcol which is zero
        """
        row, col = rowcol
        self.cells[row][col] = 0
        queue = deque([rowcol])
        visited = set()
        while queue:
            current = queue.popleft()
            cr, cc = current
            rank = self.cells[cr][cc] + 1
            visited.add(current)
            for neigh in self.get_eight_neighbors(current):
                if neigh in visited:
                    continue
                r, c = neigh
                self.cells[r][c] = rank
                queue.append(neigh)
        print(self)

    def get_eight_neighbors(self, rowcol: Tuple[int, int]) -> List[Tuple[int, int]]:
        """returns the valid Moore's neighbors that have not been assigned a value yet
        """
        row, col = rowcol
        neighbors = []
        for dr, dc in Grid.eight_offsets:
            r, c = row + dr, col + dc
            try:
                if self.cells[r][c] is None:
                    neighbors.append((r, c))
            except IndexError:
                pass
        return neighbors

    def __str__(self) -> str:
        res = []
        for row in self.cells:
            res.append(' '.join(str(elt) for elt in row))
            res.append('\n')
        return ''.join(res)


g = Grid(8, 8)
g.fill_grid_BFS((5, 5))

output:

5 5 5 5 5 5 5 5
5 4 4 4 4 4 4 4
5 4 3 3 3 3 3 3
5 4 3 2 2 2 2 2
5 4 3 2 1 1 1 2
5 4 3 2 1 0 1 2
5 4 3 2 1 1 1 2
5 4 3 2 2 2 2 2

Upvotes: 1

Arman Babaei
Arman Babaei

Reputation: 184

The property all cells labeled one is that the maximum distance in both axes is equal one, the same goes on for every cell that is if the 0 cell is on the cell (x0, y0) label of cell (x, y) will be equal to max(|x - x0|, |y - y0|)

Thus, to iterate over all labels, we can use something like this:

for (l = 0 -> min(x0, y0, N - x0, N - y0) + 1:
  for (x = x0 - l -> x0 + l)
     #checking cell (x, y0 - l)
  for (y = y0 - l -> y0 + l)
     #checking cell (x0 + l, y)
  for (x = x0 + l - 1 -> x0 + l)
     #checking cell (x, y0 + l)
  for (y = y0 - l -> y0 + l)
     #checking cell (x0 - l, y)
  #checking cell (x0 - l, y0 + l)

you can merge loops iterating over x and y if you don't care that you iterate over adjacent cells.

ps: loop ranges are assumed to be closed on start and open in end. i.e. (x = a -> b) means range (a, a+1, ..., b-1)

Upvotes: 0

Related Questions