Find minimum distance to reach nearest 0 - Java-fries
Given a matrix of -1's and 0's, display matrix which contains minimum distance to reach nearest 0 for that particular position.
Example:
Input matrix:
-1 0 -1
-1 -1 -1
-1 -1 -1
Distance matrix:
1 0 1
2 1 2
3 2 3
Not good implementation at all.
Right approach: find all zeros, then do bfs.
Given a matrix of -1's and 0's, display matrix which contains minimum distance to reach nearest 0 for that particular position.
Example:
Input matrix:
-1 0 -1
-1 -1 -1
-1 -1 -1
Distance matrix:
1 0 1
2 1 2
3 2 3
Not good implementation at all.
Right approach: find all zeros, then do bfs.
private static int[][] findDistanceMatrix(int[][] matrix) {
List<Position> positions = findPositionsOfZero(matrix);
int[][] distanceMatrix = new int[matrix.length][matrix[0].length];
for (int row = 0; row < matrix.length; row++) {
for (int col = 0; col < matrix[0].length; col++) {
distanceMatrix[row][col] = getTheShortestDistance(row, col,
positions);
}
}
return distanceMatrix;
}
private static int getTheShortestDistance(int row, int col,
List<Position> positions) {
int shortestDistance = Integer.MAX_VALUE;
for (Position position : positions) {
int distance = Math.abs(row - position.getRowIndex())
+ Math.abs(col - position.getColIndex());
if (distance < shortestDistance)
shortestDistance = distance;
}
return shortestDistance;
}
private static List<Position> findPositionsOfZero(int[][] matrix) {
List<Position> positions = new ArrayList<Position>();
int rowLen = matrix.length;
int colLen = matrix[0].length;
for (int row = 0; row < rowLen; row++) {
for (int col = 0; col < colLen; col++) {
if (matrix[row][col] == 0)
positions.add(new Position(row, col));
}
}
return positions;
}
private static class Position {
int rowIndex;
int colIndex;
public Position(int rowIndex, int colIndex) {
this.rowIndex = rowIndex;
this.colIndex = colIndex;
}
public int getRowIndex() {
return rowIndex;
}
public int getColIndex() {
return colIndex;
}
}
Read full article from Find minimum distance to reach nearest 0 - Java-fries