Find Path

FindPath

Below is the code for solving the above problem:

package com.pract.hakerrank;


public class FindThePath {

	int[][] matrix = {{0,0,0,0,0},
			{1,9,9,9,1},
			{0,0,0,0,0}};
	int rows, columns;
	int V;
	
	
	public FindThePath(int rows, int columns) {
		this.rows = rows;
		this.columns = columns;
		
		//matrix = new int[rows][columns];
		V = rows * columns;
	}
	
	public int getMinDistance(boolean[] sptSet, int[] dist){
		int index = -1;
		int minWeight = Integer.MAX_VALUE;
		
		for(int i = 0; i < V; i++){
			if(!sptSet[i] && dist[i] < minWeight){
				minWeight = dist[i];
				index = i;
			}
		}
		
		return index;
	}
	
	
	public void printTotalWeight(int src, int dest){
		
		//initialize distance matrix
		int[] dist = new int[V];
		for(int i = 0; i < V; i++){
			dist[i] = Integer.MAX_VALUE;
		}
		
		// initialize all boolean matrix
		boolean[] sptSet = new boolean[V];
		
		int row1 = src / columns;
		int column1 = src % columns;
		
		dist[src] = matrix[row1][column1];
	
		// update distance matrix and find the solution
		for(int u = 0; u < V; u++){
			
			int cellNo = getMinDistance(sptSet, dist);
			
			sptSet[cellNo] = true;
			
			int row = cellNo / columns;
			int column = cellNo % columns;
			
			// now check all possibilities i.e. (row+1, col), (row-1, col), (row, col + 1), (row, col - 1)
			if((row + 1) < rows){
				
				if(checkIfReachedAtSolutionElseUpdateDistanceArray(row + 1, column, dest, sptSet, dist, cellNo)){
					System.out.println("Solution reached");
					int v = (row+1) * columns + column;
					System.out.println(dist[v]);
					return;
				}
			}
			if((row - 1) >= 0){
				if(checkIfReachedAtSolutionElseUpdateDistanceArray(row - 1, column, dest, sptSet, dist, cellNo)){
					System.out.println("Solution reached");
					int v = (row-1) * columns + column;
					System.out.println(dist[v]);
					return;
				}
			}
			if((column + 1) < columns){
				if(checkIfReachedAtSolutionElseUpdateDistanceArray(row, column + 1, dest, sptSet, dist, cellNo)){
					System.out.println("Solution reached");
					int v = row * columns + (column + 1);
					System.out.println(dist[v]);
					return;
				}
			}
			if((column - 1) >= 0){
				if(checkIfReachedAtSolutionElseUpdateDistanceArray(row, column - 1, dest, sptSet, dist, cellNo)){
					System.out.println("Solution reached");
					int v = row * columns + (column - 1);
					System.out.println(dist[v]);
					return;
				}
			}
		}
	}


	private boolean checkIfReachedAtSolutionElseUpdateDistanceArray(int row, int column, int dest, boolean[] sptSet, int[] dist, int cellNo) {

		int v = row * columns + column;
		
		if(!sptSet[v] && dist[cellNo] + matrix[row][column] < dist[v]){
			dist[v] = dist[cellNo] + matrix[row][column];
		}
		
		if(v == dest)
			return true;
		
		return false;
	}



	public static void main(String[] args) {
		
		FindThePath path = new FindThePath(3, 5);
		
		int rowSrc = 1;
		int colSrc = 1;
		
		int rowDest = 1;
		int colDist = 3;
		
		int src = rowSrc * path.columns + colSrc;
		int dest = rowDest * path.columns + colDist;
		
		path.printTotalWeight(src, dest);
	}
}

Leave a Reply