Binary Matrix find all cells with distance k

user_3181365 0
Viewed 441

I have a binary matrix with 0 and 1, and given integer K >=0. Now I want to find all possible cells which are at a maximum distance of K from cells with the value 1 and mark them as some letter 'x'.

The distance between cells A[5][2] and A[1][4] is |1-5|+|4-2|=6.

Example:

A 8x8 matrix and K = 2, cells with value 1 at (2,2) and (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

Output:

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

This is my logic which I am attempting:

find the cell position for 1 and find all cells starting from row -k till +k for given column. Similarly find all cells with given row and columns ranging from -k till +k. So for above example, for (2,2) the cells based on my logic are (0,2), (1,2), (2,2), (3,2) , (4,2) and then (2,0) , (2,1) , (2,2) , (3,2), (4,2).

But I am not able to understand how to get the remaining cells surrounding (2,2) which are (1,1), (1,3) and (3,1) , (3,3).

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

In case you do not care about the performance, the solution could be straightforward.

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);
}
user_34613970

Try this.

static void markNeighbors(char[][] matrix, int k) {
    int rows = matrix.length, cols = matrix[0].length;
    new Object() {

        void set(int x, int y) {
            for (int r = Math.max(0, x - k), rr = Math.min(rows, x + k + 1); r < rr; ++r)
                for (int s = k - Math.abs(r - x), c = Math.max(0, y - s), cc = Math.min(cols, y + s + 1); c < cc; ++c)
                    if (matrix[r][c] == '0')
                        matrix[r][c] = 'x';
        }

        void find() {
            for (int i = 0; i < rows; ++i)
                for (int j = 0; j < cols; ++j)
                    if (matrix[i][j] == '1')
                        set(i, j);
        }
    }.find();
}

and

char[][] matrix = {
    {'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'},
};

markNeighbors(matrix, 2);

for (char[] row : matrix)
    System.out.println(Arrays.toString(row));

output:

[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]
Admin1

If you decompose each group of x-es into four triangles: one triangle consisting of k x-es above the central 1 and all x-es to the right from those; and remaining three triangles resulting from rotating that first one around the 1;

and you realize each row of the triangle is one 'x' shorter than the previous one;

then the algorithm appears:

for a,b being a position of '1'
    for i in 1 .. k
        for j in 1 .. (k - i + 1)
            set 'x' at (a+j, b-i)
            set 'x' at (a+i, b+j)
            set 'x' at (a-j, b+i)
            set 'x' at (a-i, b+j)

Remember to check resulting coords against the array range and not to set 'x' where another '1' is.

user_7336370
Related