Problem: Given an M × N binary matrix, replace all occurrences of 0’s by 1’s, which are completely surrounded by 1’s from all sides (top, left, bottom, right, top-left, top-right, bottom-left, and bottom-right).
Example:
1 1 1 1 1 0 0 1 1 1 0 1 1 0 1 1
will become:
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
Approach: This is a similar problem to Surrounding regions where we used Flood Fill to resolve the problem. It's just here the cells are connected diagonally too. We just need to take care of it.
Implementation in C#:
private static void ReplaceSurroundingZeroes(int[][] matrix)
{
int rows = matrix?.Length ?? 0;
if (rows == 0)
{
return;
}
int cols = matrix[0].Length;
// top boundary
for (int i = 0; i < cols; ++i)
{
if (matrix[0][i] == 0)
{
FloodFill(matrix, 0, i, 0, -1);
}
}
// left boundary
for (int i = 0; i < rows; ++i)
{
if (matrix[i][0] == 0)
{
FloodFill(matrix, i, 0, 0, -1);
}
}
// bottom boundary
for (int i = 0; i < cols; ++i)
{
if (matrix[rows - 1][i] == 0)
{
FloodFill(matrix, rows - 1, i, 0, -1);
}
}
// right boundary
for (int i = 0; i < rows; ++i)
{
if (matrix[i][cols - 1] == 0)
{
FloodFill(matrix, i, cols - 1, 0, -1);
}
}
for (int i = 0; i < rows; ++i)
{
for (int j = 0; j < cols; ++j)
{
if (matrix[i][j] == 0)
{
FloodFill(matrix, i, j, 0, 1);
}
}
}
for (int i = 0; i < rows; ++i)
{
for (int j = 0; j < cols; ++j)
{
if (matrix[i][j] == -1)
{
matrix[i][j] = 0;
}
}
}
}
private static void FloodFill(int[][] matrix, int row, int col, int prevInt, int newInt)
{
if (!IsValidCell(matrix, row, col, prevInt))
{
return;
}
int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
matrix[row][col] = newInt;
for(int i = 0; i < dx.Length; ++i)
{
FloodFill(matrix, row + dx[i], col + dy[i], prevInt, newInt);
}
}
private static bool IsValidCell(int[][] matrix, int row, int col, int target)
{
return row >= 0 &&
row < matrix.Length &&
col >= 0 &&
col < matrix[0].Length &&
matrix[row][col] == target;
}
Complexity: O(m * n)
No comments:
Post a Comment