java - 在数字迷宫中找到最短路径，Java

Question

在数字迷宫中，玩家总是从左上角的方格开始，并进行一定数量的移动，如果存在解决方案，则将他/她带到标有“目标”的方格。迷宫中每个单元格中的值表示玩家必须从当前位置水平或垂直移动多远。我的任务是找出到达标记为“目标”的单元格的最短路径并打印它。

输入迷宫是方形二维阵列的形式。目标方格在迷宫描述中用数字 -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)

请帮忙修复代码，使解决方案成为最短路径？!

Answer 1

搜索了BFS之后，现在知道DFS和BFS的区别了。DFS算法从源点到最后一个节点走一条路径，如果发现目标就停止，否则再尝试从源点到最后一个节点的另一条路径，如此循环，直到达到目标。当BFS算法从源到下一级时，如果找到目标则停止，否则进入下一级，依此类推。对于我的问题，BFS 是寻找最短路径的合适算法。修改后的代码:

public class findShoretstPath
{
    private static class Node 
    {
        private int[] coordinate = new int[2];
        private int data;
        private Node Right, Left, Top, Bottom;
        public Node(){}
    }


public static boolean isLinked(Node s, Node d) //method to determine if the node d is linked to the node s
{
    if(d.Right == s) return true;
    if(d.Bottom == s) return true;
    if(d.Left == s) return true;
    if(d.Top == s) return true;
    return false;
}

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 void shortestPath(Node[][] nodes, int x, int y)
{
    Stack<Node> stack = new Stack<>();
    Queue<Node> queue = new LinkedList<>();
    int[][] path = new int[nodes.length][nodes[0].length];
    boolean b = false;
    int level = 1;//to keep tracking each level viseted
    queue.add(nodes[x][y]);
    path[x][y] = level;
    while(!queue.isEmpty())
    {
        Node temp;
        level++;
        int size = queue.size();
        for(int i = 0; i<size; i++)
        {
            temp = queue.remove();
            if(temp.data == -1) {b = true; break;}
            if(temp.Right != null && path[temp.Right.coordinate[0]][temp.Right.coordinate[1]] == 0)
            {
                queue.add(temp.Right);
                path[temp.Right.coordinate[0]][temp.Right.coordinate[1]] = level;
            }
            if(temp.Bottom != null && path[temp.Bottom.coordinate[0]][temp.Bottom.coordinate[1]] == 0)
            {
                queue.add(temp.Bottom);
                path[temp.Bottom.coordinate[0]][temp.Bottom.coordinate[1]] = level;
            }
            if(temp.Left != null && path[temp.Left.coordinate[0]][temp.Left.coordinate[1]] == 0)
            {
                queue.add(temp.Left);
                path[temp.Left.coordinate[0]][temp.Left.coordinate[1]] = level;
            }
            if(temp.Top != null && path[temp.Top.coordinate[0]][temp.Top.coordinate[1]] == 0)
            {
                queue.add(temp.Top);
                path[temp.Top.coordinate[0]][temp.Top.coordinate[1]] = level;
            }
        }
        if(b) break;
    }
    if(b)
    {
        int x1 = 0, y1 = 0;
        for(int i = 0; i<nodes.length; i++)// to locate the position of the goal
            for(int j = 0; j<nodes.length; j++)
                if(nodes[i][j].data == -1)
                {
                    x1 = i; y1 = j;
                }
        stack.add(nodes[x1][y1]);
        int d = path[x1][y1];
        while(d > 0)//go back from the goal to the source
        {
           for(int i = 0; i<path.length; i++)
           {
               if(path[x1][i] == d-1 && isLinked(nodes[x1][y1], nodes[x1][i]))
               {
                  stack.add(nodes[x1][i]);
                  y1 = i;
                  break;
               }
               else if(path[i][y1] == d-1 && isLinked(nodes[x1][y1], nodes[i][y1]))
               {
                  stack.add(nodes[i][y1]);
                  x1 = i;
                  break;
               }
           }
           d--;
        }
        Node temp;
        int stackSize = stack.size();
        for(int i = 0; i<stackSize; i++)// print the final result
        {
           temp = stack.pop();
           System.out.print("("+temp.coordinate[0]+" "+temp.coordinate[1]+") ");
        }
    }
    else System.out.print("No Solution Possible.");
}
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);
        shortestPath(net, 0, 0));
        System.out.println("");
}
}

现在的输出是:

(0 0) (1 0) (2 0) (3 0) (4 0) (4 4)