侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【BFS】怪物森林

GabrielxD
2023-04-15 / 0 评论 / 0 点赞 / 93 阅读 / 778 字
温馨提示:
本文最后更新于 2023-04-15,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

试题 算法提高 怪物森林


经历千辛万苦,JiaoShou 终于来到了爱琳大陆的怪物森林。

怪物森林是一个 N×MN\times M 的矩阵,从上到下一共有 NN 行,从左到右一共有 MM 列。

对于每个位置 (x,y)(x,y) 都有一个怪物,每个怪物都有一定的攻击力。

现在 JiaoShou 想要从左上角 (1,1)(1,1) 移动到右下角 (N,M)(N,M)

JiaoShou可以往上下左右四个方向移动,当然前提是不能移动出边界。

对于一条从 (1,1)(1,1)(N,M)(N,M) 的移动路线,由于森林的特殊性,JiaoShou 只能选择该路线中攻击力最小的一个怪物进行攻击,并定义该怪物的攻击力为该路线的重要度。

现在 JiaoShou 想要选择一条重要度最大的路线,请你回答 JiaoShou 的询问。

输入

第一行有两个数 N,MN, M ,表示森林的大小,用一个空格隔开。

接下来 NN 行,每行 MM 个数,第 i+1i+1jj 列的数表示位置为 (i,j)(i,j) 的怪物的攻击力。

输出

第一行输出一个数表示重要度最大的路线的重要度。

样例输入

2 2
7 5
3 4

样例输出

4

样列解释

选择 $$(1,1) \rightarrow (1,2) \rightarrow (2,2)$$ 的路线可获得最大的重要度。

数据规模和约定

  • 对于 20%20\% 的数据: N,M10N,M\le10
  • 对于 70%70\% 的数据: N,M500N,M\le500
  • 对于 100%100\% 的数据: N,M800N,M\le800 ,所有怪物的攻击力在 long int 范围内

解题

方法一:BFS

思路

BFS ,但是在状态中追加路线的重要度,然后使用优先队列(依照路线重要度排序)存储状态达到类似启发式搜索的效果,这样以来就可以让每一次选择都在重要度上达到最优。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int[][] DIRS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    static int n, m;
    static long[][] g;
    static boolean[][] vis;

    static class State {
        int x, y;
        long imp;

        public State(int x, int y, long imp) {
            this.x = x;
            this.y = y;
            this.imp = imp;
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); m = in.nextInt();
        g = new long[n][m];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                g[i][j] = in.nextLong();
            }
        }
        vis = new boolean[n][m];
        vis[0][0] = true;
        Queue<State> pq = new PriorityQueue<>((a, b) -> Long.compare(b.imp, a.imp));
        pq.offer(new State(0, 0, g[0][0]));
        while (!pq.isEmpty()) {
            State s = pq.poll();
            int x = s.x, y = s.y;
            if (x == n - 1 && y == m - 1) {
                System.out.println(s.imp);
                return;
            }
            for (int[] DIR : DIRS) {
                int nx = x + DIR[0], ny = y + DIR[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny]) continue;
                vis[nx][ny] = true;
                pq.offer(new State(nx, ny, Math.min(s.imp, g[nx][ny])));
            }
        }
    }
}
0

评论区