java - 导航 2D 数组时，检查相邻元素是否存在相对于入口点的有效路径？

Question

此问题的性质自提交以来已发生变化，但该问题不适合删除。我已回答了以下问题并将其标记为社区帖子。

我正在编写一个递归路径导航函数，我需要的最后一部分涉及了解您来自哪个单元格，并确定下一步要去哪里。

舞台

给您一个二维数组，其中 0's 表示无效路径，1's 表示有效路径。据我所知，您可以操作正在导航的数组的数据，因此我用 2's 标记了一条行驶路径。

目标

您需要递归地查找并打印从origin到exit的所有路径。有四个迷宫，有些有多条路径、死胡同或循环。

我编写的代码可以正确处理所有三种情况，但查找下一条路径的方法有缺陷，因为它从相对于当前索引的固定位置开始，并检查行进路径；如果你遇到它，它应该会撤退。

虽然这在大多数情况下有效，但在它检查的第一个地方恰好是您来自的地方时，它会失败。此时，它返回并提前结束。

因此，我需要找到一种方法，根据您来自的位置智能地开始扫描(顺时针或逆时针)，以便该位置始终是最后检查的位置。

这里是一些描述该过程的代码(注意:边缘情况在此之前处理，所以我们不需要担心):

private static void main()
{
    int StartX = ;//Any arbitrary X
    int StartY = ;//Any arbitrary Y
    String Path = ""; //Recursive calls will tack on their location to this and print only when an exit path is found.
    int[][] myArray = ;//We are given this array, I just edit it as I go
    Navigator(StartX, StartY, Path, myArray);
}

private static void Navigator(int locX, int locY, String Path, int[][] myArray)
{
    int newX = 0; int newY = 0;
    Path = Path.concat("["+locX+","+locY+"]");

//Case 1: You're on the edge of the maze
    boolean bIsOnEdge = (locX == 0 || locX == myArray.length-1 || locY == 0 || locY == myArray[0].length-1);
    if (bIsOnEdge)
    {
        System.out.println(Path);
        return;
    }

    int[][] Surroundings = surroundingsFinder(locX, locY, myArray);

    for (int i = 0; i <= 7; i++)
    {
//Case 2: Path encountered
        if (Surroundings[0][i] == 1) 
        {
            myArray[locX][locY] = 2;
            newX = Surroundings[1][i];
            newY = Surroundings[2][i];
            Navigator(newX, newY, myArray, Path);
        }

//Case 3: Breadcrumb encountered
        if (Surroundings[0][i] == 2)
        {
            myArray[locX][locY] = 1;
            return;
        }
    }
}

//generates 2D array of your surroundings clockwise from N to NW
//THIS IS THE PART THAT NEEDS TO BE IMPROVED, It always starts at A.
//
//  H A B
//  G - C
//  F E D
//
static int[][] surroundingsFinder(int locX, int locY, int[][] myArray)
{
    int[][] Surroundings = new int[3][8];
    for (int i = -1; i <= 1; i++)
    {
        for (int j = -1; j <= 1; j++)
        {

        }
    }

    //Can be done simpler, is done this way for clarity
    int xA = locX-1; int yA = locY; int valA = myArray[xA][yA];
    int xB = locX-1; int yB = locY+1; int valB = myArray[xB][yB];
    int xC = locX; int yC = locY+1; int valC = myArray[xC][yC];
    int xD = locX+1; int yD = locY+1; int valD = myArray[xD][yD];
    int xE = locX+1; int yE = locY; int valE = myArray[xE][yE];
    int xF = locX+1; int yF = locY-1; int valF = myArray[xF][yF];
    int xG = locX; int yG = locY-1; int valG = myArray[xG][yG];
    int xH = locX-1; int yH = locY-1; int valH = myArray[xH][yH];

    int[][] Surroundings = new int[3][8];
    Surroundings[0][0] = valA; Surroundings[1][0] = xA; Surroundings[2][0] = yA;
    Surroundings[0][1] = valB; Surroundings[1][1] = xB; Surroundings[2][1] = yB;
    Surroundings[0][2] = valC; Surroundings[1][2] = xC; Surroundings[2][2] = yC;
    Surroundings[0][3] = valD; Surroundings[1][3] = xD; Surroundings[2][3] = yD;
    Surroundings[0][4] = valE; Surroundings[1][4] = xE; Surroundings[2][4] = yE;
    Surroundings[0][5] = valF; Surroundings[1][5] = xF; Surroundings[2][5] = yF;
    Surroundings[0][6] = valG; Surroundings[1][6] = xG; Surroundings[2][6] = yG;
    Surroundings[0][7] = valH; Surroundings[1][7] = xH; Surroundings[2][7] = yH;

    return Surroundings;
}

有人可以帮我解决这个问题吗？如您所见，surroundingsFinder 始终首先找到 A，然后是 B，一直到 H。当且仅当您从 H 输入时才可以。但是，如果您从 A 输入的情况失败，那么我需要找到一种方法来智能地确定从哪里开始查找。一旦我知道了这一点，我就可以调整逻辑，这样我也不再使用二维值数组。但到目前为止我还无法想出智能搜索器的逻辑!

注意:我知道Java没有优化中间递归。对于这样的问题，尾递归似乎不可能起作用。

Answer 1

解决方案

最初的目标是从头到尾打印退出数组的所有路径。

该脚本的早期版本在踩踏位置上写了“0”而不是“2”，但出于某种原因，我认为我需要“2”，并且我需要区分“踩踏路径”和“无效路径” 。

事实上，由于问题的递归性质，我发现实际上可以只写 0 来解决问题。另外，我不再需要跟踪我来自哪里，我不再需要在矩阵上顺时针检查，而是从左到右遍历我周围的 3x3 矩阵，跳过我自己的单元格。

这是此类解决方案的完整代码。它在找到导出(边缘)时打印到控制台，否则在迷宫中跟踪自身，完成递归。要启动该函数，您将获得一个 0's 的方形 2D 数组。和1's哪里1是有效路径且 0是无效的。您还会获得一组“放入”的坐标( locX 、 locY )和一个用于累积坐标的空字符串，形成一条稍后打印出来的路径( String Path = "" )

这是代码:

static void Navigator(int locX, int locY, int[][] myArray, String Path)
{
    int newX = 0;
    int newY = 0;

    Path = Path.concat("["+locX+","+locY+"]");

    if ((locX == 0 || locX == myArray.length-1 || locY == 0 || locY == myArray[0].length-1))
    {//Edge Found
        System.out.println(Path);
        pathCnt++;
        myArray[locX][locY] = 1;
        return;
    }

    for (int row = -1; row <= 1; row++)
    {            
        for (int col = -1; col <= 1; col++)
        {
            if (!(col == 0 && row == 0) && (myArray[locX+row][locY+col] == 1))
            {   //Valid Path Found
                myArray[locX][locY] = 0;
                Navigator(locX+row, locY+col, myArray, Path);
            }
        }
    }

    //Dead End Found
    myArray[locX][locY] = 1;
    return;
}       System.out.println(Path);
        pathCnt++;
        swamp[locX][locY] = 1;
        return;
    }

    for (int row = -1; row <= 1; row++)
    {            
        for (int col = -1; col <= 1; col++)
        {
            if (!(col == 0 && row == 0) && (swamp[locX+row][locY+col] == 1))
            {   //Valid Path Found
                swamp[locX][locY] = 0;
                Navigator(locX+row, locY+col, swamp, Path);
            }
        }
    }

    //Dead End Found
    swamp[locX][locY] = 1;
    return;
}

正如您自己确定的那样，每次我们“进入”一个单元格时，我们都会检查 8 个邻居的有效性。首先，为了节省运行时间并避免在 for 循环期间超出数组(如果 myArray[i][j] 或 i 将其指向外部，则找不到 j，并且会出错)，我们检查边缘。由于我们已经知道了沼泽的面积，因此我们使用了一个事实比较语句，其本质上是( "(am I on the top or left edge?) or (am I on the bottom or right edge?)" )。如果我们处于边缘，我们会打印出我们所持有的路径(感谢 deep copy ，我们拥有原始 Path 的唯一副本，仅当我们处于边缘时才打印，并且包括我们的全套路径坐标)。

如果我们没有处于边缘，那么我们就会开始环顾四周。我们从左上角开始，水平移动到右下角，并进行特殊检查以确保我们没有检查我们站立的位置。:

A B C
D . E
F G H

此循环仅检查 1's并且只有在发生这种情况时才再次调用该函数。为什么？因为这是倒数第二个案例。只会发生一种额外的情况，如果我们到达函数的末尾，则意味着我们遇到了这种情况。为什么要编写额外的代码(检查 0's 以专门识别它？

所以，正如我刚才提到的，如果我们退出 for循环，这意味着我们根本没有遇到任何 1。这意味着我们被零包围了!这意味着我们已经进入了死胡同，这意味着我们所要做的就是从函数的该实例中出错，因此最终的return; .

总而言之，最终的功能很简单。但是，如果没有任何背景，必须认识到这些案例的模式和含义，并且经过多次失败的尝试，这可能需要相当多的工作。我花了几天时间来完善这个。

祝大家编码愉快!