迷宫救人——DFS小题

原创

题目大意：人质被困在迷宫之中，要求你寻找一条最短路径快速找到人质。

如图，人质在黄色点2处，营救者在起点红色处，1表示无法通过的障碍点，寻找一条最短路径快速找到人质。

毫无疑问用DFS，遍历4个方向，比较每条可以找到人质的路径即可得到答案。

 import java.util.Scanner;

 public class Maze_rescue {

     static int n;    //行

     static int m;    //列

     static int min=99999;

     static int maze[][];

     static int flag[][];    //1代表已走过

     static int dir[][]= {{0,1},{1,0},{0,-1},{-1,0}};    //右、下、左、上

     static void dfs(int x,int y,int step) {    //step代表步数

         if(maze[x][y]==2) {    //找到人质

             if(step<min) {

                 min=step;

             }

             return;

         }

         for(int i=0;i<4;i++) {

             int dx=x+dir[i][0];

             int dy=y+dir[i][1];

             if(dx<0 || dy<0 || dx>=n || dy>=m) {    //越界

                 continue;

             }

             if(maze[dx][dy]==1 || flag[dx][dy]==1) {    //判断是否障碍点或已走过点

                 continue;

             }

             flag[dx][dy]=1;    //标志此点已经走过

             dfs(dx,dy,step+1);

             flag[dx][dy]=0;    //回溯

         }

     }

     public static void main(String[] args) {

         Scanner reader=new Scanner(System.in);

         n=reader.nextInt();

         m=reader.nextInt();

         maze=new int[n][m];    //编号从（0,0）开始

         flag=new int[n][m];    //标记路径的数组

         flag[0][0]=1;    //起点不算入步数

         for(int i=0;i<n;i++) {    //建造迷宫，0表示空地，1表示障碍,2代表人质点

             for(int j=0;j<m;j++) {

                 maze[i][j]=reader.nextInt();

             }

         }

         dfs(0,0,0);

         System.out.println(min);

     }

 }

12:11:00

2018-07-15