Tuesday 9 September 2014

Program to find shortest distance to particular value in a matrix

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.


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

Position.java

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




No comments:

Post a Comment