根据与某个单元格的接近度循环遍历 NxN 网格单元格

Question

我有一个 N by N 网格。我有一个标有 0 的特定网格单元格：

我打算遍历网格单元格，从 0 单元格开始，顺序如下：

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

如何编写循环？

我试图遵循这个 post。但是我无法根据自己的情况对其进行调整。

Answer 1

属性所有标记为 1 的单元格是两个轴上的最大距离等于 1，如果 0 单元格在单元格 (x0, y0) 标签上，则每个单元格也是如此单元格 (x, y) 的大小将等于 max(|x - x0|, |y - y0|)

因此，要遍历所有标签，我们可以使用这样的方法：

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)

如果您不关心迭代相邻单元格，您可以合并 loops 迭代 x 和 y。

ps：假定循环范围在开始时关闭并在结束时打开。即 (x = a -> b) 表示范围 (a, a+1, ..., b-1)

Answer 2

您可以使用 Breadth First Search 填充整个网格：从值为零的单元格开始，它将以同心波扩展，向远离中心的每个后续层添加一个。

这里有一个例子 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

根据与某个单元格的接近度循环遍历 NxN 网格单元格

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

language-agnostic

algorithm

loops

nested-loops

输出：