有一个n*m格的迷宫(表示有n行、m列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这n*m个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。
请统一用 左上右下的顺序拓展，也就是 (0,-1),(-1,0),(0,1),(1,0)
第一行是两个数n，m( 1 < n ， m < 15 )，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。
所有可行的路径，描述一个点时用(x，y)的形式，除开始点外，其他的都要用“->”表示方向。
如果没有一条可行的路则输出-1。
5 6 1 0 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 5 6
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
【算法分析】
用一个a数组来存放迷宫可走的情况，另外用一个数组b来存放哪些点走过了。每个点用两个数字来描述，一个表示行号，另一个表示列号。对于某一个点(x，y)，四个可能走的方向的点描述如下表：
2
1 x,y 3
4
对应的位置为：(x, y-1)，(x-1, y)，(x, y+1)，(x+1, y)。所以每个点都要试探四个方向，如果没有走过(数组b相应的点的值为0)且可以走(数组a相应点的值为1)同时不越界，就走过去，再看有没有到达终点，到了终点则输出所走的路，否则继续走下去。
这个查找过程用search来描述如下：
procedure search(x, y, b, p)；{x，y表示某一个点，b是已经过的点的情况，p是已走过的路}
begin
for i:＝1 to 4 do{分别对4个点进行试探}
begin
先记住当前点的位置，已走过的情况和走过的路；
如果第i个点(xl，y1)可以走，则走过去；
如果已达终点，则输出所走的路径并置有路可走的信息，
否则继续从新的点往下查找search(xl，y1，b1，p1)；
end；
end；
有些情况很明显是无解的，如从起点到终点的矩形中有一行或一列都是为0的，明显道路不通，对于这种情况要很快地“剪掉”多余分枝得出结论，这就是搜索里所说的“剪枝”。从起点开始往下的一层层的结点，看起来如同树枝一样，对于其中的“枯枝”——明显无用的节点可以先行“剪掉”，从而提高搜索速度。
1 public class 走迷宫 { 2 static final int N=17; 3 static int q[][]=new int[N][N]; 4 static boolean vis[][]=new boolean[N][N]; 5 static int n; 6 static int m; 7 static int dx[]={0,-1,0,1}; 8 static int dy[]={-1,0,1,0}; 9 static int a; //a和b为起点的坐标 10 static int b; 11 static boolean flag;//记录是否有路 12 public static void main(String[] args) { 13 Scanner sc=new Scanner(System.in); 14 n=sc.nextInt(); 15 m=sc.nextInt(); 16 for(int i=1;i<=n;i++){ 17 for(int j=1;j<=m;j++){ 18 q[i][j]=sc.nextInt(); 19 } 20 } 21 a=sc.nextInt(); 22 b=sc.nextInt(); 23 int x2=sc.nextInt(); 24 int y2=sc.nextInt(); 25 dfs(a,b,x2,y2); 26 if(flag==false){ //没有路 27 System.out.println(-1); 28 } 29 } 30 static void dfs(int x1,int y1,int x2,int y2){ 31 //出口 打印所有走过的路 32 if(x1==x2 && y2==y1){ 33 flag=true; 34 System.out.printf("(%d,%d)",a,b); //因为起点没有标记 所以输出时候不要忘了起点 35 for(int i=1;i<=n;i++){ 36 for(int j=1;j<=m;j++){ 37 if(vis[i][j]==true) System.out.printf("->(%d,%d)",i,j); 38 } 39 } 40 System.out.println(); 41 return; 42 } 43 for(int i=0;i<4;i++){ 44 int x=x1+dx[i]; 45 int y=y1+dy[i]; 46 if(!vis[x][y] && q[x][y] == 1 && x>=1 && x<=n && y>=1 && y<=m){ //x，y要满足边界条件 47 vis[x][y]=true; 48 dfs(x,y,x2,y2); 49 vis[x][y]=false; 50 } 51 } 52 } 53 }
原文：https://www.cnblogs.com/w12312/p/14531430.html