algorithm - 基于与某个单元格的接近度循环遍历 NxN 个网格单元格

Question

我有一个N按N网格。我有一个标有0：

我打算按0以下顺序循环网格单元格，从单元格开始：

• 从标记的单元格开始0
• 下一个单元格被标记1
• 下一个单元格被标记2
• ...
• 直到到达网格边界

我怎样才能组成循环？

---

我试图关注这篇文章。但我无法调整它以适应我的情况。

标签： algorithmloopslanguage-agnosticnested-loops

Answer 1

您可以使用广度优先搜索填充整个网格：从值为 0 的单元格开始，它将以同心波扩展，向远离中心的每个后续层添加一个。

这是一个例子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))

输出：

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