1

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

输入迷宫是方形二维数组的形式。目标方格由迷宫描述中的数字 -1 表示。输出 对于迷宫，输出迷宫的解或短语“No Solution Possible”。解决方案应输出为格式为“（行，列）”的方坐标列表，按照从开始到目标的访问顺序，包括起始单元格。您将需要报告从开始到目标的最短解决方案。最短的解决方案将是唯一的。我尝试了一些解决方案，但我认为存在的问题是解决方案始终是我发现的第一条路径，而不是最短的..

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)

请帮助如何修复代码，以便解决方案成为最短路径？！

4

1 回答 1

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)
于 2019-06-12T19:29:35.190 回答