CODEWITHSUNDEEP
javarecursionpath-finding
Nzed
Nzed

Reputation: 109

Path finding in a finite grid

I have a 7x7 grid (of a city). I want to travel from a starting point (x1, y1) to a destination point (x2, y2) and show the path as an output in the form of multiple (x, y) strings separated by comas. I want to do this using RECURSION and output true if the path exists and false otherwise.
How should I do that? I'm thinking of making 4 methods that check 4 directions. Any input would be appreciated.

For now, I have just implemented the constructor of my class:-

    map = new boolean[row][column];

    for(int i = 0; i < 7; i++)
    {
        for(int j = 0; j < 7; j++)
        { 
            map[i][j] = false; 
        }
    }

Upvotes: 3

Views: 235

Answers (2)

user8234870
user8234870

Reputation: 

import java.io.PrintStream;

/**
 * Dev Parzival
 * Date : 27/10/2020 Time : 18:28
 * I have a confidence about my life that comes from standing tall on my own two feet.
 */

public class Path {
    static PrintStream out=System.out;
    static boolean pathfound=false;
    //////////Main/////////
    public static void main(String $[]){
        boolean arr[][]=new boolean[5][5];
        for(int i=0;i<arr.length;i++)
            for(int j=0;j<arr[0].length;j++) {
                if (i==j)
                    arr[i][j] = true;
//                if(j==arr[0].length-1)
//                    arr[i][j]=true;
            }
        travel(arr,0,0,arr.length-1,arr[0].length-1);
        if(pathfound)
            out.println("Path is found");
        else
            out.println("Path is not found");
    }

    static boolean travel(boolean a[][],int r,int c,int targetR,int targetC){

        //Target is found
        if(r==targetR && c==targetC){
            pathfound=true;
        }
        //South
        if(!pathfound && r+1<a.length)
            if(a[r+1][c]){
                a[r+1][c]=false;
                pathfound=travel(a,r+1,c,targetR,targetC);
            }
        //North
        if(!pathfound && r-1>=0)
            if(a[r-1][c]){
                a[r-1][c]=false;
                pathfound=travel(a,r-1,c,targetR,targetC);
            }
        //East
        if(!pathfound && c+1<a[0].length)
            if(a[r][c+1]){
                a[r][c+1]=false;
                pathfound=travel(a,r,c+1,targetR,targetC);
            }
        //West
        if(!pathfound && c-1>=0)
            if(a[r][c-1]){
                a[r][c-1]=false;
                pathfound=travel(a,r,c-1,targetR,targetC);
            }
        //North-West
        if(!pathfound && c-1>=0 && r-1>=0)
            if(a[r-1][c-1]){
                a[r-1][c-1]=false;
                pathfound=travel(a,r-1,c-1,targetR,targetC);
            }
        //Noth-East
        if(!pathfound && c+1<a[0].length && r-1>=0)
            if(a[r-1][c+1]){
                a[r-1][c+1]=false;
                pathfound=travel(a,r-1,c+1,targetR,targetC);
            }
        //South-East
        if(!pathfound && c+1<a[0].length && r+1<a.length)
            if(a[r+1][c+1]){
                a[r+1][c+1]=false;
                pathfound=travel(a,r+1,c+1,targetR,targetC);
            }
        //South-West
        if(!pathfound && c-1>=0 && r+1<a.length)
            if(a[r+1][c-1]){
                a[r+1][c-1]=false;
                pathfound=travel(a,r+1,c-1,targetR,targetC);
            }
        //Print the cell position
        if(pathfound)
            out.println(r+" "+c);
        return pathfound;
    }
}

Above code will find a path between starting cell and the destination cell if path exists.

Output it generates:

4 4
3 3
2 2
1 1
0 0
Path is found

Upvotes: 0

user8234870
user8234870

Reputation: 

import java.io.PrintStream;

/**
 * Dev Parzival
 * Date : 27/10/2020 Time : 18:28
 * I have a confidence about my life that comes from standing tall on my own two feet.
 */

public class Path {
    static PrintStream out=System.out;
    static boolean pathfound=false;
    //////////Main/////////
    public static void main(String $[]){
        boolean arr[][]=new boolean[5][5];
        for(int i=0;i<arr.length;i++)
            for(int j=0;j<arr[0].length;j++) {
                if (i==0)
                    arr[i][j] = true;
                if(j==arr[0].length-1)
                    arr[i][j]=true;
            }
        travel(arr,0,0,arr.length-1,arr[0].length-1);
        if(pathfound)
            out.println("Path is found");
        else
            out.println("Path is not found");
    }
    
    static boolean travel(boolean a[][],int r,int c,int targetR,int targetC){
    //Target is found
    if(r==targetR && c==targetC){
        pathfound=true;
    }
    //South
    if(!pathfound && r+1<a.length)
        if(a[r+1][c]){
            a[r+1][c]=false;
            pathfound=travel(a,r+1,c,targetR,targetC);
        }
    //North
    if(!pathfound && r-1>=0)
        if(a[r-1][c]){
            a[r-1][c]=false;
            pathfound=travel(a,r-1,c,targetR,targetC);
        }
    //East
    if(!pathfound && c+1<a[0].length)
        if(a[r][c+1]){
            a[r][c+1]=false;
            pathfound=travel(a,r,c+1,targetR,targetC);
        }
    //West
    if(!pathfound && c-1>=0)
        if(a[r][c-1]){
            a[r][c-1]=false;
            pathfound=travel(a,r,c-1,targetR,targetC);
        }
        if(pathfound)
            out.println(r+" "+c);
        return pathfound;
    }
}

I will advice make a copy of original array so values will not be modified. I have tested above code works fine .This approach is known as flood fill .Search more about depth first search in graph.

Upvotes: 1

Related Questions