Find minimum distance to reach nearest 0 - Java-fries
Problem: 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
Problem: 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
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;
}
Read full article from Find minimum distance to reach nearest 0 - Java-fries