java - 矩阵中递归下、右、左、上移动导致堆栈溢出异常

Question

该程序用于找出矩阵中两点之间的最短路径，其中我向下、向右、向左和向上遍历，但由于递归，它进入了来回的无限循环。

这个程序基本上遍历矩阵，其中

• “C”表示目的地
• “B”表示来源
• “_”表示允许移动
• “D”表示不允许

问题是找到 B 和 C 之间最短的浴槽。

我怎样才能让这段代码工作？如一次后停止控件向下移动。

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 1

详细阐述 Frank Puffer 的想法:

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

这修复了“_”字段的覆盖，但仍然覆盖了“B”。由于最短路径的长度为 4 并且您减去 1，因此程序会打印 3。