100DaysOfCode/Maze.java at main · ashish2675/100DaysOfCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package backtracking;

import java.util.ArrayList;

public class Maze {
    public static void main(String[] args) {

        boolean [][] board = {
                {true, true, true},
                {true, false, true},
                {true, true, true},
        };
//        System.out.println(count(3,3));
//        path("", 3, 3);
//        System.out.println(pathRet("", 3, 3));
//        System.out.println(pathRetDiagonal("", 3, 3));
        pathRestrictions("", board, 0 , 0);
    }


    // normal maze paths
    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);
        return left +right;
    }


    //Printing the paths
    static void path(String p, int r, int c){
        if(r == 1 && c == 1){
            System.out.println(p);
            return;
        }
        if(r>1){
            path(p + 'D', r-1, c);
        }
        if(c>1){
            path(p + 'R', r, c-1);
        }
    }


    // Printing the paths in an arraylist
    static ArrayList<String> pathRet(String p, int r, int c){
        if(r == 1 && c == 1){
            ArrayList<String> list = new ArrayList<>();
            list.add(p);
            return list;
        }
        ArrayList<String> list = new ArrayList<>();
        if(r>1){
            list.addAll(pathRet(p + 'D', r-1, c));
        }
        if(c>1){
            list.addAll(pathRet(p + 'R', r, c-1));
        }
        return list;
    }


    // When we allow diagonals
    static ArrayList<String> pathRetDiagonal(String p, int r, int c){
        if(r == 1 && c == 1){
            ArrayList<String> list = new ArrayList<>();
            list.add(p);
            return list;
        }
        ArrayList<String> list = new ArrayList<>();
        if(r>1 && c>1){
            list.addAll(pathRetDiagonal(p + 'D', r-1, c-1));
        }

        if(r>1){
            list.addAll(pathRetDiagonal(p + 'V', r-1, c));
        }
        if(c>1){
            list.addAll(pathRetDiagonal(p + 'H', r, c-1));
        }
        return list;
    }

    //River Flowing
    static void pathRestrictions(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;
        }
        if(r< maze.length-1){
            pathRestrictions(p + 'D', maze, r+1, c);
        }
        if(c<maze[0].length-1){
            pathRestrictions(p + 'R', maze, r, c+1);
        }
    }
}