Maze Problem - Backtracking

A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N-1]. 
A rat starts from source and has to reach destination. The rat can move only in two directions: forward and down.
In the maze matrix, 0 means the block is dead end and 1 means the block can be used in the path from source to destination.

Find the path that rat should take from source to destination.





/* Java program to solve Rat in a Maze problem using
backtracking */

public class Maze {

    final int N = 4;

    /*
     * A utility function to print solution matrix sol[N][N]
     */
    void printSolution(int sol[][]) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(" " + sol[i][j] + " ");
            }
            System.out.println();
        }
    }

    /*
     * A utility function to check if x,y is valid index for N*N maze
     */
    boolean isSafe(int maze[][], int x, int y) {
        // if (x,y outside maze) return false
        return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
    }

    /*
     * This function solves the Maze problem using Backtracking. It mainly uses
     * solveMazeUtil() to solve the problem. It returns false if no path is
     * possible, otherwise return true and prints the path in the form of 1s.
     * Please note that there may be more than one solutions, this function
     * prints one of the feasible solutions.
     */
    boolean solveMaze(int maze[][]) {
        int sol[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } };

        if (solve(maze, 0, 0, sol) == false) {
            System.out.print("Solution doesn't exist");
            return false;
        }

        printSolution(sol);
        return true;
    }

    /*
     * A recursive utility function to solve Maze problem
     */
    boolean solve(int maze[][], int x, int y, int sol[][]) {
        // if (x,y is goal) return true
        if (x == N - 1 && y == N - 1) {
            sol[x][y] = 1;
            return true;
        }

        // Check if maze[x][y] is valid
        if (isSafe(maze, x, y) == true) {
            // mark x,y as part of solution path
            sol[x][y] = 1;

            /* Move forward in x direction */
            if (solve(maze, x + 1, y, sol)) {
                return true;
            }

            /*
             * If moving in x direction doesn't give solution then Move down in
             * y direction
             */
            if (solve(maze, x, y + 1, sol)) {
                return true;
            }

            /*
             * If none of the above movements work then BACKTRACK: unmark x,y as
             * part of solution path
             */
            sol[x][y] = 0;
            return false;
        }

        return false;
    }

    public static void main(String args[]) {
        Maze rat = new Maze();
        int maze[][] = { { 1, 0, 0, 0 }, { 1, 1, 0, 1 }, { 0, 1, 0, 0 }, { 1, 1, 1, 1 } };
        rat.solveMaze(maze);
    }
}

Comments

Post a Comment

Popular posts from this blog

Java important topics list for interviews

These are some of the important concepts you need to be very clear with , when you attend any interviews for bigger companys. Try to understand each of these concepts with some real world examples.  Basic Concepts: Class vs Interface vs Abstract class.  Static variables. final variables. Access modifiers - Public, Private, Default, Protected.  Immutable Strings and String manipulation concepts. Object lifecycle - How objects are created and destroyed. Threads: Thread Dump analysis Producer Consumer problem Dead lock problem Synchronisation Thread creation lifecycle Priority Sleep IsAlive Join Core: JVM Internals ClassLoaders Reflections Periodic task threads GC threads Compiler threads Signal dispatcher thread Design Patterns: Singleton Adapter Lazy loading Builder vs fluent  Observer Patterns Heap Management: Young Generation Old Generation (also called Tenured Generation) Permanent Generat...
Read more

Tough Sql practise questions for interviews involving SELECT queries - Part 2

Consider the following relational schema. An employee can work in more than one department; the pct_time filed of the Works relation shows the percentage of time that a given employee works in a given department. Emp( eid: integer , ename: string , age: integer , salary: real ) Works( eid: integer , did: integer , pct_time: integer ) Dept( did: integer , dname: string , budget: real , managerid: integer ) Write the following queries in SQL: Print the names and ages of each employee who works in both the Hardware department and the Software department. For each department with more than 20 full-time-equivalent employees (i.e., where the part-time and full-time employees add up to at least that many full- time employees), print the did together with the number of employees that work in that department. Print the name of each employee whose salary exceeds the budget of all of the departments that he or she works in. ...
Read more

DBMS important topics list for interviews

In any real world application, DBMS plays a key role for managing your data. Its very important to have a strong idea about these topics and have a handson with this. Important topics that needs to be covered to prepare any dbms interviews are as below. Core Concepts:  Normalization forms - Questions related to designing a database for a real world application will be asked. They test your design skills. You need to be thorough with 3N form designing. Other questions related 1N,2N forms can be expected.  Query questions - Select, Insert, Updated , Delete related questions with combinations of joins will be asked. Following combinations will be asked.  Inner Join Outer join Self join Group By ,  Having clause Between, In, Like IsNull, Null Union Intersect Basics of PL/Sql. Inbuilt sql functions. How indexing works internally.  Few basics of distributed mysql management.  So make sure you are clear with above concepts befor...
Read more

Program to find number lines and words in a given file

import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; import java.util.StringTokenizer; public class LineWordCount { public void calculate(String fileName) throws FileNotFoundException { long lineCount = 0; long wordCount = 0; Scanner scanner = null; try { scanner = new Scanner(new FileInputStream(fileName)); while (scanner.hasNextLine()) { String line = scanner.nextLine(); lineCount++; wordCount += new StringTokenizer(line, " ").countTokens(); } } catch (Exception ex) { ex.printStackTrace(); } finally { if (scanner != null) { scanner.close(); } } System.out.println(lineCount + "," + wordCount); } public static void main(String[] args) throws FileNotFoundException { String fileName = "filepath/file.txt"; new LineWordCount().calculate(fileName); } }
Read more

Tough Sql practise questions for interviews involving SELECT queries - Part 1

The following relations keep track of airline flight information: Flights( flno: integer , from: string , to: string , distance: integer , departs: time , arrives: time , price: integer ) Aircraft( aid: integer , aname: string , cruisingrange: integer ) Certified(eid: integer , aid: integer ) Employees( eid: integer , ename: string , salary: integer ) Note that the Employees relation describes pilots and other kinds of employees aswell; every pilot is certified for some aircraft, and only pilots are certified to fly.Write each of the following queries in SQL. Find the names of aircraft such that all pilots certified to operate them earn more than $80,000. For each pilot who is certified for more than three aircraft, find the eid and the maximum cruisingrange of the aircraft for which she or he is certified. Find the names of pilots whose salary is less than the price of the cheapest route from Los Angeles to Honolulu. ...
Read more

Producer Consumer Problem with Blocking Queue in Java.

Producer consumer problem is one of the most important problems which is asked in many interviews. Simplest way to solve this problem is to use Blocking Queue. Code can be viewed here. import java.io.File; import java.util.concurrent.BlockingQueue; import java.util.concurrent.LinkedBlockingQueue; public class ProducerConsumer { public static void main(String args[]) { // Creating shared object BlockingQueue<String> sharedQueue = new LinkedBlockingQueue<String>(2); // Note the Same sharedQueue is being passed to Producer as well as // Consumer // Creating Producer and Consumer Thread Thread prodThread = new Thread(new Producer(sharedQueue), "ProcuerThread"); Thread consThread = new Thread(new Consumer(sharedQueue), "ConsumerThread"); // Starting producer and Consumer thread prodThread.start(); consThread.start(); } } // Producer Class in java class Producer implements Runnable { private final Blocking...
Read more

Animation for String search - KMP Algorithm

This is a beautiful and interactive animation to understand how KMP Algorithm works. Mix and match with different inputs and give a try. Failure Function: Represents function to lookup if there is a mismatch in pattern and txt strings. Search Button: Represents how search works . Animation for KMP Algorithm Credits & Copyright to : This is an embedded link from http://www.cs.usfca.edu/ . Credits to original contributor as given in below copyright. Copyright 2011 David Galles. Copyright 2015 Yves Lucet. Available under the FreeBSD license.
Read more

Interactive Data Structure visualizations/animations for algorithms

These are the beautiful and interactive animations to understand various data structure algorithms. Mix and match with different inputs and give a try. If you have any doubts about how these algorithms work, drop a comment. Will get back to you. Visualizations for Data-structure algorithms Credits & Copyright to : This is an embedded link from http://www.cs.usfca.edu/ . Credits to original contributor as given in below copyright. Copyright 2011 David Galles. Copyright 2015 Yves Lucet. Available under the FreeBSD license.
Read more

Replace Occurances of the given string

package strings; /* Given a string str that may contain one more occurrences of “AB”.  Replace all occurrences of “AB” with “C” in str . This should be in the same array.  Solution should be optimized Dont try to shift entire elements or something. Examples: Input  : str = "helloABworld" Output : str = "helloCworld" Input  : str = "fghABsdfABysu" Output : str = "fghCsdfCysu" */ public class ReplaceOccurances {     static char [] replace( char [] str ) {         int len = str . length ;         if ( len < 2)             return str ;         int i = 0; // Index in modified string         int j = 0; // Index in original string         // Traverse string         while ( j < len - 1) {           ...
Read more