我尝试在 java 中简单地实现该算法。我的结论是你描述的算法有效，即使是寻找多条路径。或者，你可能想出了一个比我更聪明的测试用例。（请张贴您的迷宫，以便我可以尝试我的算法）
我的死胡同计数器的实现可能不是最有效的，但它完成了工作。对于访问的每个当前 OPEN 节点，它会检查 4 个周围节点：
- 如果至少有一个邻居是 OPEN，则当前节点不是死胡同
- 如果访问了多个邻居，则当前节点不是死胡同
- 如果只有一个节点被访问（我们在上一步中来自的那个）并且没有其他邻居是 OPEN，则当前节点是死胡同
这是我写的java代码（当心！很长）。如果您愿意，另一种方法是将路径存储在堆栈上，每次将节点设置为 VISITED 时推送一个节点，并在每次将其设置回 OPEN 时弹出一个节点。每次达到 GOAL 时，应复制并保存保存当前路径的堆栈。
如果删除了标记为“dead-end-investigation-step”的 if 块，则此实现几乎完全等于问题中描述的实现。
package test;
import java.util.HashSet;
import java.util.Set;
public class MazeSolver {
final static int OPEN = 0;
final static int WALL = 1;
final static int GOAL = 2;
final static int VISITED = 3;
static int[][] field = { { 0, 0, 0, 0, 0, 1 }, { 1, 0, 1, 1, 0, 1 },
{ 1, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 2 }, { 1, 0, 1, 0, 0, 0 } };
// This is what the field looks like:
//
// 0 1 1 0 1
// 0 0 0 0 0
// 0 1 1 0 1
// 0 1 0 0 0
// 0 0 0 1 0
// 1 1 0 2 0
static int width = field.length;
static int height = field[0].length;
static int xStart = 0;
static int yStart = 0; // Initiated to start position: (x = 0, y = 0)
static int nrSolutions = 0; // Records number of solutions
// Used for storing id:s of dead end nodes.
// The integer id is (x + y * width)
static Set<Integer> deadEnds = new HashSet<Integer>();
public static void main(String[] arg) {
System.out.println("Initial maze:");
printField();
findPath(xStart, yStart);
System.out.println("Number of solutions: " + nrSolutions);
System.out.println("Number of dead ends: " + deadEnds.size());
}
private static void findPath(int x, int y) {
if (x < 0 || y < 0 || x >= width || y >= height) { // Step 1
return;
} else if (field[x][y] == GOAL) { // Step 2
nrSolutions++;
System.out.println("Solution nr " + nrSolutions + ":");
printField();
return;
} else if (field[x][y] != OPEN) { // Step 3
return;
} else if (isDeadEnd(x, y)) { // Extra dead-end-investigation-step
int uniqueNodeId = x + y * width;
deadEnds.add(uniqueNodeId); // Report as dead end
return;
}
field[x][y] = VISITED; // Step 4
findPath(x, y - 1); // Step 5, go north
findPath(x + 1, y); // Step 6, go east
findPath(x, y + 1); // Step 7, go south
findPath(x - 1, y); // Step 8, go west
field[x][y] = OPEN; // Step 9
// Step 10 is not really needed, since the boolean is intended to
// display only whether or not a solution was found. This implementation
// uses an int to record the number of solutions instead.
// The boolean return value would be (nrSolutions != 0)
}
private static boolean isDeadEnd(int x, int y) {
int nrVisitedNeighbours = 0;
if (y > 0) { // If northern neighbour exists
if (field[x][y - 1] == VISITED) {
nrVisitedNeighbours++;
} else if (field[x][y - 1] != WALL) {
return false;
}
}
if (x < width - 1) { // If eastern neighbour exists
if (field[x + 1][y] == VISITED) {
nrVisitedNeighbours++;
} else if (field[x + 1][y] != WALL) {
return false;
}
}
if (y < height - 1) { // If southern neighbour exists
if (field[x][y + 1] == VISITED) {
nrVisitedNeighbours++;
} else if (field[x][y + 1] != WALL) {
return false;
}
}
if (x > 0) { // If western neighbour exists
if (field[x - 1][y] == VISITED) {
nrVisitedNeighbours++;
} else if (field[x - 1][y] != WALL) {
return false;
}
}
if (nrVisitedNeighbours > 1) { // Circular path scenario
return false;
}
return true; // The exhaustive result of this check: this is a dead
// end
}
private static void printField() {
for (int yy = 0; yy < field[0].length; yy++) {
for (int xx = 0; xx < field.length; xx++) {
System.out.print(field[xx][yy] + " ");
}
System.out.println();
}
System.out.println();
}
}
上面的算法报告了四个不同的解决方案路径和两个死角，示例迷宫被硬编码到代码中。
<EDIT>
解决方案路径太少的原因可能是对什么是解决方案路径的误解？例如，考虑这个迷宫：
######
## #
## # #
#S #
##E###
######
这个迷宫只有一个有效的解法路径。这是因为您只能访问每个节点一次，因此绕过圆形路径不是有效的解决方案路径，因为这将访问 S 以东和 E 以北的节点两次。您使用的算法暗示了解决方案路径的这种定义。
如果允许多次访问同一个节点，则将有无限多的解决方案，因为您可以绕圈 1、2、3 ... 无限次。
</编辑>
<编辑2>
正如您所说，每次将节点设置为 VISITED 时都会增加 pathLength，并且每次将 VISITED 节点设置回 OPEN 时都会减小路径长度。
为了记录最短路径长度，我还有一个 shortestPath int 值，我将其初始化为 Integer.MAX_VALUE。然后，每次我达到目标时，我都会这样做：
if(pathLength < shortestPath){
shortestPath = pathLength;
}
至于死胡同……我试着用手数了一下，我觉得 9 似乎是对的。这是Sareen发布的迷宫，但死角（手工）用 D 标记：
####################
#S # D# D#D D#
# # ## ## ### ###
# # # # #
## # # # ## #
# ### ##### #
# # #D #D # ###
# ### ### ## # #####
# D#D #D E#
####################
你还能找到更多吗？还是我误解了你所说的死胡同？我认为死胡同意味着：你只能从一个方向到达的节点。
示例 1：
######
## ###
## ###
## ###
#S E#
######
上面的迷宫有一个死胡同。
示例 2：
######
## ##
## ##
## ##
#S E#
######
上面的迷宫没有死胡同。即使您位于最北端的可访问节点之一，仍然有两个相邻的非 WALL 方格。
你对死胡同有另一种定义吗？
</EDIT2>