Given a matrix of -1's and 0's, display a matrix which contains minimum distance to reach nearest 0 from that particular position.
Example:
Input1:
-1,0,-1
-1,-1,-1
-1,-1,-1
Output:
1,0,1
2,1,2
3,2,3
Input2:
-1,0,-1
-1,-1,-1
-1,0,-1
Output:
1,0,1
2,1,2
1,0,1
Algorithm:
1. Figure out the all positions in matrix having zero and cache them.
2. Calculate the distance from each position to the cached zero positions by summing absolute distance of x and y co-ordinates.
3. Put the minimum value in the result matrix.
Example:
Input1:
-1,0,-1
-1,-1,-1
-1,-1,-1
Output:
1,0,1
2,1,2
3,2,3
Input2:
-1,0,-1
-1,-1,-1
-1,0,-1
Output:
1,0,1
2,1,2
1,0,1
Algorithm:
1. Figure out the all positions in matrix having zero and cache them.
2. Calculate the distance from each position to the cached zero positions by summing absolute distance of x and y co-ordinates.
3. Put the minimum value in the result matrix.
package
com.prasune.coding;
import java.util.ArrayList;
import
java.util.List;
public class
ShortestDistance {
public static void main(String[]
args) {
int matrix[][] =
{
{-1,0,-1},
{-1,-1,-1},
{-1,0,-1}
};
printAsMatrix(matrix);
printDistanceToZero(matrix);
}
private static void
printDistanceToZero(int[][] matrix) {
int[][]
resultMatrix = new int[matrix.length][matrix.length];
List<Position> zeroPositions
= new ArrayList<Position>();
for (int i = 0; i <
matrix.length; i++) {
for (int j = 0; j <
matrix[i].length; j++) {
if(matrix[i][j]
== 0){
zeroPositions.add(new
Position(i,j));
}
}
}
for (int i = 0; i <
matrix.length; i++) {
for (int j = 0; j <
matrix[i].length; j++) {
if(matrix[i][j]
== 0){
resultMatrix[i][j]
= 0;
} else{
int minValue =
Integer.MAX_VALUE;
for (Position
position : zeroPositions) {
int tempMinValue
= Math.abs(i - position.getRowNum()) +
Math.abs(j - position.getColNum());
if(tempMinValue
< minValue){
minValue
= tempMinValue;
}
}
resultMatrix[i][j]
= minValue;
}
}
}
printAsMatrix(resultMatrix);
}
private static void printAsMatrix(int[][] matrix) {
for (int i = 0; i <
matrix.length; i++) {
for (int j = 0; j <
matrix[i].length; j++) {
System.out.print(matrix[i][j]);
if(j <
matrix[i].length-1){
System.out.print(",");
}
}
System.out.println();
}
}
}
|
package
com.prasune.coding;
public class Position {
private int rowNum;
private int colNum;
public Position(int rowNum, int colNum) {
this.rowNum = rowNum;
this.colNum = colNum;
}
public int getRowNum() {
return rowNum;
}
public void setRowNum(int rowNum) {
this.rowNum = rowNum;
}
public int getColNum() {
return colNum;
}
public void setColNum(int colNum) {
this.colNum = colNum;
}
}
|
