首页 > 代码库 > Java迷宫问题

Java迷宫问题

Input

一个N × M的二维数组,表示一个迷宫。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。

Output

左上角到右下角的最短路径,格式如样例所示。

Sample Input

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

Sample Output

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

import java.util.*;public class Main {    public static void main(String[] args)     {        Scanner scanner = new Scanner(System.in);        while(scanner.hasNext())        {            int m = scanner.nextInt();            int n = scanner.nextInt();            int[][] map = new int[m][n];            int[][] visited = new int[m][n];            for(int i=0;i<m;i++)                for(int j=0;j<n;j++)                    map[i][j] = scanner.nextInt();            // 四个方向            int[][] dir = {{1,0},{0,1},{0,-1},{-1,0}};            Stack<Node> path = new Stack<>();            Node start = new Node(0, 0);            Node end = new Node(m-1, n-1);            visited[0][0]=1;            path.push(start);            while(!path.empty())            {                boolean flag=false;                Node peek = path.peek();                if(peek.x==end.x && peek.y==end.y)                    break;                else                {                    for(int i=0;i<4;i++)                    {                        Node ne = new Node(peek.x+dir[i][0] , peek.y+dir[i][1]);                        if(ne.x>=0 && ne.x<m && ne.y>=0 && ne.y<n &&                                map[ne.x][ne.y]==0 && visited[ne.x][ne.y]==0)                        {                            path.push(ne);                            visited[ne.x][ne.y]=1;                            flag=true;                            break;                        }                    }                    // 找到一个方向                    if(flag)                    {                        continue;                    }                    // 都没有方向                    path.pop();                }            }            Iterator<Node> it = path.iterator();            while(it.hasNext())            {                Node outNode=it.next();                System.out.println("("+outNode.x+","+outNode.y+")");            }        }        scanner.close();    }    }class Node{    int x;    int y;    Node(int x, int y)    {        this.x = x;        this.y = y;    }}

 

Java迷宫问题