欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

迷宫救人——DFS小题

程序员文章站 2023-11-07 10:35:34
原创 题目大意:人质被困在迷宫之中,要求你寻找一条最短路径快速找到人质。 如图,人质在黄色点2处,营救者在起点红色处,1表示无法通过的障碍点,寻找一条最短路径快速找到人质。 毫无疑问用DFS,遍历4个方向,比较每条可以找到人质的路径即可得到答案。 1 import java.util.Scanner ......

原创

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

迷宫救人——DFS小题

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

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

迷宫救人——DFS小题
 1 import java.util.Scanner;
 2 
 3 public class Maze_rescue {
 4     
 5     static int n;    //行
 6     static int m;    //列
 7     static int min=99999;
 8     static int maze[][];
 9     static int flag[][];    //1代表已走过
10     static int dir[][]= {{0,1},{1,0},{0,-1},{-1,0}};    //右、下、左、上
11     
12     static void dfs(int x,int y,int step) {    //step代表步数
13         if(maze[x][y]==2) {    //找到人质
14             if(step<min) {
15                 min=step;
16             }
17             return;
18         }
19         for(int i=0;i<4;i++) {
20             int dx=x+dir[i][0];
21             int dy=y+dir[i][1];
22             if(dx<0 || dy<0 || dx>=n || dy>=m) {    //越界
23                 continue;
24             }
25             if(maze[dx][dy]==1 || flag[dx][dy]==1) {    //判断是否障碍点或已走过点
26                 continue;
27             }
28             flag[dx][dy]=1;    //标志此点已经走过
29             dfs(dx,dy,step+1);
30             flag[dx][dy]=0;    //回溯
31         }
32     }
33     
34     public static void main(String[] args) {
35         
36         Scanner reader=new Scanner(System.in);
37         n=reader.nextInt();
38         m=reader.nextInt();
39         maze=new int[n][m];    //编号从(0,0)开始
40         flag=new int[n][m];    //标记路径的数组
41         flag[0][0]=1;    //起点不算入步数
42         for(int i=0;i<n;i++) {    //建造迷宫,0表示空地,1表示障碍,2代表人质点
43             for(int j=0;j<m;j++) {
44                 maze[i][j]=reader.nextInt();
45             }
46         }
47         dfs(0,0,0);
48         System.out.println(min);
49     }
50 
51 }
View Code

12:11:00

2018-07-15