java在迷宫中用坐标寻找最短路径
嘿,我是一个初学者,我写的程序是寻找最短的路径,从开始到结束在二维数组。但我的问题是,我无法找到协调的完整路径。我的意思是,例如:
public static void main(String[] args) {
int[][] pom = new int[4][4];
int arr[][] =
{{0, 0, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 1, 1, 1, 1},
{0, 1, 1, 1, 1},
{0, 0, 1, 1, 1}};
int startX = 3;
int startY = 1;
int endX = 2;
int endY = 3;
int min_dist = shortestPath(arr, pom, startX, startY, endX, endY, Integer.MAX_VALUE, 0);
System.out.println(min_dist);
}
我想谈谈产出:(3,1),(3,2),(2,2),(2,3)
这是我的方法,我试着用列表来做,但仍然不知道如何做,以及如何在这个过程中正确地清除它们 (类点只有两个属性,int x和int y)
static List<Point> tmp = new ArrayList<>();
public static boolean uCanGo(int mat[][], int visited[][], int x, int y) {
if (mat[x][y] == 1 && visited[x][y] == 0) {
// tmp.add(new Point(x, y));
return true;
}
return false;
}
public static int shortestPath(int arr[][], int visited[][], int startX, int startY, int endX, int endY, int finalDistance, int currentDistance) {
if (startX == endX && startY == endY) {
return Integer.min(finalDistance, currentDistance);
}
visited[startX][startY] = 1;
if ((startY + 1 < 4) && uCanGo(arr, visited, startX, startY + 1)) {
finalDistance = shortestPath(arr, visited, startX, startY + 1, endX, endY, finalDistance, currentDistance + 1);
}
if ((startX + 1 < 4) && uCanGo(arr, visited, startX + 1, startY)) {
finalDistance = shortestPath(arr, visited, startX + 1, startY, endX, endY, finalDistance, currentDistance + 1);
}
if ((startX - 1 > 0) && uCanGo(arr, visited, startX - 1, startY)) {
finalDistance = shortestPath(arr, visited, startX - 1, startY, endX, endY, finalDistance, currentDistance + 1);
}
if ((startY - 1 > 0) && uCanGo(arr, visited, startX, startY - 1)) {
finalDistance = shortestPath(arr, visited, startX, startY - 1, endX, endY, finalDistance, currentDistance + 1);
}
visited[startX][startY] = 0;
return finalDistance;
}
抱歉出了问题,谢谢
在得到帮助后,我仍然找不到问题,例如,在该数组中应该有:(3,3)(4,3)(5,3)(6,3)(6,4)(6,5)
int arr[][] =
{{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1},
{0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1},
{0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0},
{0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1},
{0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1},
{0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1},
{0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1},
};
int startX = 3;
int startY = 3;
int endX = 6;
int endY = 5;
# 1 楼答案
由于您需要路径,我更改了方法的返回类型,并做了一些小更改: