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

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

Categories DSA