Maze Problems

We observe that left = r-1, c and right = c, r-1. For counting the total ways just return left + right.

import java.util.*;
public class Main
{
	public static void main(String[] args) {
		//int ans = count(3,3);
		//System.out.println(ans);
		
		//printPath("",3,3);
		//diagPath("",3,3);
		boolean[][] arr = {
		    {true, true, true},
		    {true, false, true},
		    {true, true, true}
		};
		obstacles("",arr,0,0);
	}
	
	// counting path
	static int count(int r, int c) {
	    if(r==1 || c==1) {
	        return 1;
	    }
	    int left = count(r-1,c);
	    int right = count(r, c-1);
	    int total = left + right;
	    return total;
	}
	
	//print path
	static void printPath(String p, int r, int c) {
	    if(r==1 && c==1) {
	        System.out.println(p);
	        return;
	    }
	    
	    if(r>1) {
	        printPath(p+"D", r-1, c);
	    } 
	    
	    if(c>1) {
	        printPath(p+"R", r, c-1);
	    } 
	}
	
    //diagonal path
    static void diagPath(String p, int r, int c) {
	    if(r==1 && c==1) {
	        System.out.println(p);
	        return;
	    }
	    
	    if(r>1 && c>1) {
	        diagPath(p+"Diagonal ", r-1, c-1);
	    }
	    
	    if(r>1) {
	        diagPath(p+"Down ", r-1, c);
	    } 
	    
	    if(c>1) {
	        diagPath(p+"Right ", r, c-1);
	    } 
	}
	
	//obstacles
	static void obstacles(String p, boolean[][] maze, int r, int c) {
	    if(r==maze.length-1 && c==maze[0].length-1) {
	        System.out.println(p);
	        return;
	    }
	    
	    if(maze[r][c]==false) {
	        return;
	    }
	    
	    if(r<maze.length-1) {
	        obstacles(p+"D", maze, r+1, c);
	    } 
	    
	    if(c<maze[0].length-1) {
	        obstacles(p+"R", maze, r, c+1);
	    } 
	}
}

Including all paths (Using Backtracking)

import java.util.Arrays;

public class AllPaths {
    public static void main(String[] args) {
        boolean[][] board = {
                {true, true, true},
                {true, true, true},
                {true, true, true}
        };
        int[][] path = new int[board.length][board[0].length];
        allPath("", board, 0, 0);
    }

    static void allPath(String p, boolean[][] maze, int r, int c) {
        if (r == maze.length - 1 && c == maze[0].length - 1) {
            System.out.println(p);
            return;
        }

        if (!maze[r][c]) {
            return;
        }

        // i am considering this block in my path
        maze[r][c] = false;

        if (r < maze.length - 1) {
            allPath(p + 'D', maze, r+1, c);
        }

        if (c < maze[0].length - 1) {
            allPath(p + 'R', maze, r, c+1);
        }

        if (r > 0) {
            allPath(p + 'U', maze, r-1, c);
        }

        if (c > 0) {
            allPath(p + 'L', maze, r, c-1);
        }

        // this line is where the function will be over
        // so before the function gets removed, also remove the changes that were made by that function
        maze[r][c] = true;
    }
}

Output

Leave a Comment