提交后，此问题的性质发生了变化，但该问题不适合删除。我已经回答了下面的问题，并将其标记为社区帖子
我正在编写一个递归路径导航函数，我需要的最后一部分是了解你来自哪个单元格，并确定下一步该去哪里。
舞台
您得到一个2d数组，其中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输入的情况下失败，那么我需要制定一种方法来智能地确定start在哪里查找。一旦我知道了这一点，我可能会调整逻辑，这样我就不再使用2D值数组了。但到目前为止，我还无法想出智能搜索器的逻辑！
注意：我知道Java不会优化中间递归。似乎不可能让尾递归处理这样的问题。
解决方案
最初的目标是从头至尾打印退出数组的所有路径。
脚本的早期版本在踩踏位置写"0"，而不是"2"，但出于某种原因，我认为我需要"2"并且我需要区分"踩踏路径"one_answers"无效路径"。
事实上，由于这个问题的递归性质，我发现你实际上可以边写0边解决这个问题。此外，我不再需要跟踪我来自哪里，我不再顺时针检查矩阵，而是从左到右迭代周围的3x3矩阵，跳过我自己的单元格。
以下是此类解决方案的完整代码。它在找到出口(边缘(后打印到控制台，然后在迷宫中跟踪自己，完成递归。要启动该函数，您将获得0's和1's的正方形2D数组，其中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循环过程中离开阵列(如果i或j指向外部，它就找不到myArray[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;。
总而言之，最后的函数很简单。但是，在没有背景的情况下，必须意识到这些案例的模式和意义，在几次尝试失败后，这可能需要相当多的工作。我花了好几天的时间来完善这个。
编码快乐，大家！
您的问题似乎是：
if (Surroundings[0][i] == 2)
{
myArray[locX][locY] = 1;
return;
}
也许这应该改为：
if (Surroundings[0][i] == 2)
{
// not sure why you need this if it's already 1
myArray[locX][locY] = 1;
// go to next iteration of the "i" loop
// and keep looking for next available path
continue;
}
当周围的单元格都不满足条件if (Surroundings[0][i] == 1)时，递归方法将自动返回。
PS:通常使用小写字母作为第一个字符来命名变量。例如：surroundings、path、startX或myVar