В числовом лабиринте игрок всегда начинает с квадрата в верхнем левом углу и делает определенное количество ходов, которые приведут его / ее к клетке, помеченной как Гол, если решение существует. Значение в каждой ячейке в лабиринте указывает, как далеко игрок должен двигаться горизонтально или вертикально от своей текущей позиции.
Моя задача - выяснить, обозначен ли кратчайший путь к ячейке с надписью «Цель», и распечатать его.
Input
лабиринт в виде квадратного двумерного массива. Квадрат ворот обозначается цифрой -1 в описании лабиринта.
Выход
Для лабиринта выведите решение лабиринта или фразу «Решение невозможно». Решения должны быть выведены в виде списка квадратных координат в формате «(строка, столбец)» в порядке их посещения из начать с цели, включая стартовую ячейку. Вам нужно будет сообщить кратчайшее решение от начала до цели. Самое короткое решение будет уникальным.
Я попробовал какое-то решение, но я думаю, что есть проблема, решение которой - всегда первый путь, который я нашел, не самый короткий ..
public class findShoretstPath
{
private static Stack<Node> stack = new Stack<>();
private static class Node
{
private int[] coordinate = new int[2];
private int data;
private Node Right, Left, Top, Bottom;
public Node(){}
}
public static boolean isValid(int[][] a, int x, int y)
{
if(x >= 0 && x < a.length && y >= 0 && y < a.length)
return true;
return false;
}
public static Node[][] nodeArray(int[][] a)
{
Node[][] nodeA = new Node[a.length][a.length];
for(int i = 0; i<nodeA.length; i++)
for(int j = 0; j<nodeA[i].length; j++)
{
nodeA[i][j] = new Node();
nodeA[i][j].coordinate[0] = i;
nodeA[i][j].coordinate[1] = j;
nodeA[i][j].data = a[i][j];
}
for(int i = 0; i<nodeA.length; i++)
for(int j = 0; j<nodeA[i].length; j++)
{
if(isValid(a, i, j+nodeA[i][j].data))
nodeA[i][j].Right = nodeA[i][j+nodeA[i][j].data];
if(isValid(a, i, j-nodeA[i][j].data))
nodeA[i][j].Left = nodeA[i][j-nodeA[i][j].data];
if(isValid(a, i+nodeA[i][j].data, j))
nodeA[i][j].Bottom = nodeA[i+nodeA[i][j].data][j];
if(isValid(a, i-nodeA[i][j].data, j))
nodeA[i][j].Top = nodeA[i-nodeA[i][j].data][j];
}
return nodeA;
}
public static boolean findPath(Node[][] s, int[][] t, int x, int y)
{
boolean b = false;
if(t[x][y] == 0)
{
t[x][y] = 1;
if(s[x][y].data == -1) b = true;
else
{
if(s[x][y].Right != null) b = findPath(s, t, x, y+s[x][y].data);
if(!b && s[x][y].Bottom != null) b = findPath(s, t, x+s[x][y].data, y);
if(!b && s[x][y].Left != null) b = findPath(s, t, x, y-s[x][y].data);
if(!b && s[x][y].Top != null) b = findPath(s, t, x-s[x][y].data, y);
}
if(b) stack.add(s[x][y]);
}
return b;
}
public static void main(String[] args)
{
int[][] maze = {{1,1,1,1,1},
{1,1,1,1,1},
{1,1,1,1,1},
{1,1,1,1,3},
{4,1,1,3,-1}};
Node[][] net = nodeArray(maze);
int[][] path = new int[maze.length][maze[0].lenght];
if(findPath(net, path, 0, 0))
{
Node temp;
while(!stack.isEmpty())
{
temp = stack.pop();
System.out.print("("+temp.coordinate[0]+" "+temp.coordinate[1]+") ");
}
}
else System.out.println("No Solution Possible.");
}
}
для этого примера вывод должен быть:
(0 0) (1 0) (2 0) (3 0) (4 0) (4 4)
но у меня есть такой вывод:
(0 0) (0 1) (0 2) (0 3) (0 4) (1 4) (2 4) (3 4) (3 1) (3 2) (3 3) (4 3) (4 0) (4 4)
Пожалуйста, помогите как исправить код, чтобы решение было кратчайшим путем?!