yogas yogas - 3 months ago 14
Java Question

Moving down, right, left and up in matrix recursively causes stack overflow exception

the program is for finding out the shortest path between two points in a matrix,
wherein i traverse down,right, left and up but due to recursion it goes into an infinite loop coming back and forth.

this program basically traverses through the matrix where


  • 'C' denotes destination

  • 'B' denotes source

  • '_' denotes allowed move

  • 'D' means not allowed



the problem is to find the shortest bath between B and C.

How i can i make this code work ?? as in to stop the control to go downwards after once.

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Stockroom
{
//static int m = 0;
//static int n = 0;
//static char a[][] = new char [m][n];

public static boolean checkFeasibility(int x, int y, int row, int col, char a[][])
{
if(x>=0 && x<row && y>=0 && y<col && a[x][y] != 'D')
return true;

else
return false;
}

public static boolean shortestPath(char a[][], int bx, int by, int x, int y, int len, int minLen)
{
if( checkFeasibility(bx,by,x,y,a)==false )
return false;

if(a[bx][by]=='C')
{
minLen = Math.min(len,minLen);
System.out.println(minLen-1);
return true;
}



len++;


if(shortestPath(a,bx+1,by,x,y,len++,minLen)== true)
return true;

if(shortestPath(a,bx,by+1,x,y,len++,minLen)==true)
return true;

if(shortestPath(a,bx,by-1,x,y,len++,minLen)== true)
return true;

if(shortestPath(a,bx-1,by,x,y,len++,minLen)== true)
return true;



else {
len--;
return false;
}

}

public static void main (String[] args) throws java.lang.Exception
{
char arr[][] = {
{'_','B','_','_'},

{'D','_','_','D'},

{'_','D','_','_'},

{'_','_','C','_'},

};

int bx =0,by=1,px=3,py=2;
int n =4,m=4;

shortestPath(arr, bx, by, m, n, 0, 100);

}
}

Answer

Elaborating a bit on Frank Puffer’s idea:

class Stockroom {

    public static boolean checkFeasibility(int x, int y, int row, int col,
            char a[][]) {
        if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] != 'D')
            return true;

        else
            return false;
    }

    public static boolean shortestPath(char a[][], int bx, int by, int x,
            int y, int len, int minLen) {
        if (checkFeasibility(bx, by, x, y, a) == false)
            return false;

        if (a[bx][by] == 'C') {
            minLen = Math.min(len, minLen);
            System.out.println(minLen - 1);
            return true;
        }

        len++;

        if (len >= minLen) { // this was not shortest
            return false;
        }

        // hack to make sure we don’t go through the same spot again
        a[bx][by] = 'D';

        if (shortestPath(a, bx + 1, by, x, y, len, minLen) == true) {
            // remove temporary block so this space can be used in other paths
            a[bx][by] = '_';
            return true;
        }

        if (shortestPath(a, bx, by + 1, x, y, len, minLen) == true) {
            a[bx][by] = '_';
            return true;
        }

        if (shortestPath(a, bx, by - 1, x, y, len, minLen) == true) {
            a[bx][by] = '_';
            return true;
        }

        if (shortestPath(a, bx - 1, by, x, y, len, minLen) == true) {
            a[bx][by] = '_';
            return true;
        }

        len--;
        return false;

    }

    public static void main(String[] args) {
        // find path from B to C; don’t go through D
        char arr[][] = { { '_', 'B', '_', '_' }, 
                         { 'D', '_', '_', 'D' },
                         { '_', 'D', '_', '_' },
                         { '_', '_', 'C', '_' },
                        };

        int bx = 0, by = 1, px = 3, py = 2;
        int n = 4, m = 4;

        shortestPath(arr, bx, by, m, n, 0, 100);
        System.out.println(Arrays.deepToString(arr));
    }
}

This repairs the overwriting of '_' fields, but still overwrites the 'B'. The program prints 3 since the shortest path has length 4 and you subtract 1.

Comments