登录后台

页面导航

本文编写于 774 天前,最后修改于 774 天前,其中某些信息可能已经过时。

题目描述:少年李逍遥的婶婶病了,王小虎介绍他去一趟仙灵岛,向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛,克服了千险万难来到岛的中心,发现仙药摆在了迷阵的深处。迷阵由 M×N 个方格组成,有的方格内有可以瞬秒李逍遥的怪物,而有的方格内则是安全。现在李逍遥想尽快找到仙药,显然他应避开有怪物的方格,并经过最少的方格,而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。

输入格式
第一行输入两个非零整数 M 和 N,两者均不大于 2020。M 表示迷阵行数, N表示迷阵列数。

接下来有 M 行, 每行包含 N 个字符,不同字符分别代表不同含义:

1) '@':少年李逍遥所在的位置;2) '.':可以安全通行的方格;3) '#':有怪物的方格;4) '*':仙药所在位置。

输出格式
输出一行,该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1−1。
样例输入1
8 8
.@##...#

....#.

.#.##..

..#.###.

.#...#.

..###.#.
...#.*..
.#...###
样例输出1
10

样例输入2
6 5
.*.#.
.#...
..##.
.....
.#...
....@
样例输出2
8

样例输入3
9 6
.#..#.
.#.*.#
.####.
..#...
..#...
..#...
..#...

.@.

.#..#.
样例输出3
-1

思路:最开始用的是dfs,但提交了才发现dfs并不适合本题。dfs虽然能通过三个用例,但如果M和N的值过大的话,地图就会变得非常大,dfs就会进行很多无效的搜索,会浪费很多时间导致最后超时。因此最后改成用bfs解,代码如下:

public class Main {

//Point类的相关方法在此略过
static int m,n;
static char [][]map=new char[100][100];//地图
static boolean [][]book=new boolean[100][100];//标记每个点是否走过
static int ans=10000;
static int[]dirx={0,0,1,-1};//方向数组
static int[]diry={1,-1,0,0};
static int tx=0,ty=0;
static Point start=new Point();//起始点
static Point temp=new Point();//临时结点
static boolean judge(int x,int y){//判断是否符合要求
    if (x>=m||x<0||y>=n||y<0) return false;//越界
    if (map[x][y]=='#'||book[x][y]==true) return false;//遇到怪物或者已经走过的点
    return true;
}
static int bfs(){
    LinkedList<Point>queue=new LinkedList<>();
    queue.add(start);
    while (!queue.isEmpty()){
        Point point=queue.getFirst();
        queue.removeFirst();
        if (point.x==tx&&point.y==ty){//直接就是终点
            return point.step;
        }
        for (int i=0;i<4;i++){//遍历四个方向
            int newx=point.x+dirx[i];
            int newy=point.y+diry[i];
            if (judge(newx,newy)){
                temp.x=newx;
                temp.y=newy;
                temp.step=point.step+1;
                Point t=new Point();//不能直接将整个temp对象赋给它
                t.x=temp.x;
                t.y=temp.y;
                t.step=temp.step;
                queue.add(t);
                book[newx][newy]=true;
            }
        }
    }
    return -1;
}

public static void main(String[] args) {
    Scanner in=new Scanner(System.in);
    m=in.nextInt();
    n=in.nextInt();
    in.nextLine();
    int sx=0,sy=0;
    for (int i=0;i<m;i++){
        char[]temp=in.nextLine().toCharArray();
        for (int j=0;j<n;j++){
            map[i][j]=temp[j];
            if (map[i][j]=='@'){
                sx=i;
                sy=j;
            }
            if (map[i][j]=='*'){
                tx=i;
                ty=j;
            }
        }
    }
    for (int i=0;i<100;i++){
        for (int j=0;j<100;j++){
            book[i][j]=false;
        }
    }
    start.x=sx;
    start.y=sy;
    System.out.println(bfs());
}}



需要注意的是,JAVA与C++有所不同,在将结点入队时不能直接将全局变量temp入队,如果入队的是temp,那么只要temp的某个属性值改变一次,队列中所有元素的相应属性也会一起改变,因此要将temp的值赋给另一个Point类对象(称其为p),再将p加入队列(这里也不能直接用Point p=temp,这样会将p也设为全局变量。正确的方法应该是分别将各个属性值赋给p)