Tuesday, 15 September 2015

Minimum number of turns required in a maze. | Back tracking , Java

Dear Friends,


I am here with you with another problem based upon back tracking.

The problem is as below.

We are given a matrix of NXM size. Each Cell either contains 0 or 1. 1 represents a blockage or a Wall and 0 represents valid path. We need to reach from top left cell to the bottom right cell.
We need to out out the minimum number of turns required to reach the bottom right cell.


Friends Please find the code below.

package com.learn.dfs;

import java.util.Arrays;

public class MinimumTurns {

    public static void main(String[] args) {
        int[][] A = 
            { 
                { 0, 1, 1, 1, 0 }, 
                { 0, 0, 0, 0, 0 }, 
                { 1, 0, 0, 1, 1 }, 
                { 1, 1, 0, 0, 0 }, 
                { 0, 0, 0, 1, 0 },
                { 0, 1, 0, 1, 0 }, 
                { 0, 1, 0, 1, 0 }, 
                { 0, 0, 0, 0, 0 }, 
                { 1, 0, 0, 1, 1 }, 
                { 1, 0, 0, 0, 0 }, 
            };
        int initialDir = findInitialDirUtil(A);
        if (initialDir != -1) {
            findMinTurns(A, 0, 0, A.length, A[0].length, 0, initialDir);
            System.out.println(minTurns);
        } else {
            System.out.println("No path exists");
        }
    }

    static int minTurns = Integer.MAX_VALUE;

    public static int findInitialDirUtil(int[][] A) {
        if (A[0][1] == 0) {
            return 0;
        }
        if (A[1][0] == 0) {
            return 1;
        }
        return -1;
    }

    /**
     * A is the input matrix, with 0s and 1s. 1s represent the wall and 0s
     * represent the moving cells. The problem is to find the minimum number of
     * turns to be taken in order to reach from top left cell to bottom right
     * cell.
     * 
     * The below solution is based upon back tracking.
     * 
     * @param A
     * @param row
     * @param col
     * @param R
     * @param C
     * @param turns
     * @param currDir
     */
    public static void findMinTurns(int[][] A, int row, int col, int R, int C, int turns, int currDir) {
        if(turns >= minTurns){
            return;
        }
        
        if (row == R - 1 && col == C - 1) {
            if (turns < minTurns) {
                minTurns = turns;
            }
            return;
        }
        A[row][col] = turns;
        if (col + 1 < C && A[row][col + 1] == 0) {
            boolean isDirChanged = currDir != 0;
            int updatedDir = currDir;
            int updatedTurns = turns;
            if (isDirChanged) {
                updatedDir = 0;
                updatedTurns++;
            }
            findMinTurns(A, row, col + 1, R, C, updatedTurns, updatedDir);
        }

        if (row + 1 < R && A[row + 1][col] == 0) {
            boolean isDirChanged = currDir != 1;
            int updatedDir = currDir;
            int updatedTurns = turns;
            if (isDirChanged) {
                updatedDir = 1;
                updatedTurns++;
            }
            findMinTurns(A, row + 1, col, R, C, updatedTurns, updatedDir);
            
        }

        if (col - 1 >= 0 && A[row][col - 1] == 0) {
            boolean isDirChanged = currDir != 2;
            int updatedDir = currDir;
            int updatedTurns = turns;
            if (isDirChanged) {
                updatedDir = 2;
                updatedTurns++;
            }
            findMinTurns(A, row, col - 1, R, C, updatedTurns, updatedDir);
        }
        if (row - 1 >= 0 && A[row - 1][col] == 0) {
            boolean isDirChanged = currDir != 3;
            int updatedDir = currDir;
            int updatedTurns = turns;
            if (isDirChanged) {
                updatedDir = 3;
                updatedTurns++;
            }
            findMinTurns(A, row - 1, col, R, C, updatedTurns, updatedDir);
        }

        A[row][col] = 0;
    }
}