【BFS】怪物森林

题目

试题 算法提高 怪物森林

---

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

怪物森林是一个 $N\times M$ 的矩阵，从上到下一共有 $N$ 行，从左到右一共有 $M$ 列。

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

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

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

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

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

输入

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

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

输出

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

样例输入

2 2
7 5
3 4

样例输出

4

样列解释

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

数据规模和约定

• 对于 $20\%$ 的数据： $N,M\le10$
• 对于 $70\%$ 的数据： $N,M\le500$
• 对于 $100\%$ 的数据： $N,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])));
            }
        }
    }
}