java - 二元矩阵查找距离为 k 的所有单元格

Question

我有一个包含 0 和 1 的二进制矩阵，并给定整数 K >=0。现在我想找到与值为 1 的单元格最大距离为 K 的所有可能单元格，并将它们标记为某个字母“x”。

单元格 A[5][2] 和 A[1][4] 之间的距离为 |1-5|+|4-2|=6。

示例:

一个 8x8 矩阵，K = 2，单元格的值为 1，位于 (2,2) 和 (6,6)

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0

输出:

0 0 x 0 0 0 0 0
0 x x x 0 0 0 0
x x 1 x x 0 0 0
0 x x x 0 0 0 0
0 0 x 0 0 0 x 0
0 0 0 0 0 x x x
0 0 0 0 x x 1 x
0 0 0 0 0 x x x

这是我正在尝试的逻辑:

查找 1 的单元格位置，并查找给定列从行 -k 到 +k 的所有单元格。同样查找具有给定行和列的所有单元格，范围从 -k 到 +k。因此，对于上面的示例，对于 (2,2)，根据我的逻辑，单元格是 (0,2)、(1,2)、(2,2)、(3,2) 、(4,2) 然后 ( 2,0)、(2,1)、(2,2)、(3,2)、(4,2)。

但我无法理解如何获取 (2,2) 周围的剩余单元格，即 (1,1)、(1,3) 和 (3,1) 、(3,3)。

Matrix is of size m rows and n cells in range 1 to 500
K range is 1 to 1000

Answer 1

如果您不关心性能，解决方案可能很简单。

public static void markAllCellsWithDistance(char[][] matrix, int k) {
    for (int row = 0; row < matrix.length; row++)
        for (int col = 0; col < matrix[row].length; col++)
            if (matrix[row][col] == '1')
                markCells(matrix, k, row, col);
}

private static void markCells(char[][] matrix, int k, int row1, int col1) {
    for (int row2 = 0; row2 < matrix.length; row2++)
        for (int col2 = 0; col2 < matrix[row2].length; col2++)
            if (matrix[row2][col2] == '0' && distance(row1, col1, row2, col2) <= k)
                matrix[row2][col2] = 'x';
}

private static int distance(int row1, int col1, int row2, int col2) {
    return Math.abs(row1 - row2) + Math.abs(col1 - col2);
}