端盘子问题（二分查找+广度优先）

题目描述

终于中午放学铃声打响了，小明想要尽快地前往食堂打自己最喜欢吃的菜。小明觉得能打到喜欢吃的菜越多越好，他会准备好若干个盘子再出发，带了几个盘子就打几份菜。但是一路上人群拥挤程度不同，如果太过拥挤，小明会拿不稳太多盘子。

经过观察，小明发现食堂的地形可以用一个 n × n 的二维平面表示：

• 初始位置是 (1,1)。
• 食堂的位置是 (n,n)。
• 在除开初始位置和食堂位置外的所有格子上，都有一个最大允许的盘子数量，表示小明在经过该格子时最多能带的盘子数量。如果小明带的盘子数量超过这个限制，会被人群挤掉，前功尽弃。

小明只能在二维平面内行走，并且每次可以花费 1 秒，从当前位置 (i, j) 移动到相邻的 (i+1, j)、(i, j+1)、(i-1, j) 或 (i, j-1)。

你需要帮助小明找到：

• 在 T 秒内从起点 (1,1) 走到终点 (n,n) 时，最多能带多少个盘子。

如果无论如何也不能在规定时间内到达终点，输出 0。

---

输入描述

第一行包含两个整数 n 和 T，分别表示：

• n：二维平面的大小为 n × n
• T：时间限制（秒数）

接下来 n 行，每行包含 n 个整数，描述每个位置的最大允许盘子数量：

• 如果某位置的值为 -1，表示没有限制（即可以带任意数量的盘子）。
• 起点 (1,1) 和终点 (n,n) 的值为 -1。
• 其他格子的值为 >= 0，表示该位置的最大允许盘子数量。

输入约束：

• 1≤n≤10001≤n≤1000
• 1≤T≤n21≤T≤n2
• −1≤ai,j≤1,000,000−1≤a**i,j≤1,000,000（仅 (1,1) 和 (n,n) 的值为 -1）

---

输出描述

输出一行，表示小明最多能带的盘子数量。
如果无论如何也不能在规定时间内到达终点，输出 0。

样例输入

4 6
-1 2 1 1
0 2 2 0
0 0 2 2
1 1 0 -1

---

样例输出

2

---

解释

在样例输入中，小明需要在 6 秒内从 (1,1) 走到 (4,4)。
经过仔细计算，最多可以携带 2 个盘子，否则某些位置的限制无法满足。

提示

1. 二分查找+广度优先搜索（BFS）

   是解决这个问题的有效方法：

   • 使用 二分查找 来找到可以带的最大盘子数量。
   • 每次假设一个盘子数量，用 BFS 检查是否能在规定时间内从起点走到终点。

2. 时间复杂度优化：由于 n 最大可以达到 1000，路径搜索需要高效的算法，所以 BFS 是更合适的选择。

解题：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {// 四个方向的移动向量，分别表示：向下，向上，向右，向左static int[] dx = {1, -1, 0, 0};static int[] dy = {0, 0, 1, -1};// 定义全局变量n（表示二维平面的大小）和T（表示时间限制）static int n, T;// 定义二维数组grid，用来存储每个格子允许的最大盘子数量static int[][] grid;public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 读取n和Tn = sc.nextInt();T = sc.nextInt();grid = new int[n][n];// 读取地图数据，即每个格子允许的最大盘子数量for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {grid[i][j] = sc.nextInt();}}// 进行二分查找，查找能带的最大盘子数量int left = 0;       // 二分查找的左边界，最小值是0int right = 1000000; // 二分查找的右边界，最大值为1000000（题目允许的最大值）int result = 0;     // 用来记录最终能带的最大盘子数量// 开始二分查找while (left <= right) {// 取当前的中间值mid，表示我们假设小明能带mid个盘子int mid = (left + right) / 2;// 调用canReach函数判断：带mid个盘子能否在规定的时间T内到达终点if (canReach(mid)) {// 如果可以到达，说明mid是一个可行的解，记录结果并尝试更大的值result = mid;left = mid + 1;  // 尝试更大的盘子数量} else {// 如果不能到达，说明mid过大，需要尝试更小的值right = mid - 1;}}// 输出最后找到的最大盘子数量System.out.println(result);}/*** 判断是否可以带至少k个盘子，在不超过T秒的情况下从(1,1)到达(n,n)* @param k: 假设要带的盘子数量* @return: 是否可以在T秒内到达终点*/private static boolean canReach(int k) {// 使用队列进行广度优先搜索（BFS）Queue<int[]> queue = new LinkedList<>();// 用一个二维数组visited来标记某个位置是否被访问过，防止重复搜索boolean[][] visited = new boolean[n][n];// 起点是(0, 0)，即(1,1)的位置，初始时间为0queue.offer(new int[]{0, 0, 0});visited[0][0] = true;  // 标记起点已经访问过// 开始BFS搜索while (!queue.isEmpty()) {int[] current = queue.poll();  // 取出队列中的当前点int x = current[0], y = current[1], time = current[2]; // 当前的x, y坐标和已消耗的时间// 如果已经超过时间限制，继续检查下一个可能的位置if (time > T) {continue;}// 如果已经到达终点（n-1, n-1），返回true，表示带k个盘子可以成功到达if (x == n - 1 && y == n - 1) {return true;}// 向四个方向移动，分别是：下、上、右、左for (int i = 0; i < 4; i++) {int nx = x + dx[i];  // 新的x坐标int ny = y + dy[i];  // 新的y坐标// 检查新位置是否在二维平面内，并且没有访问过if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {// 检查新位置是否允许带k个盘子，起点和终点没有限制（值为-1）if (grid[nx][ny] == -1 || grid[nx][ny] >= k) {// 标记新位置为已访问，并加入队列继续搜索visited[nx][ny] = true;queue.offer(new int[]{nx, ny, time + 1});  // 时间加1}}}}// 如果搜索结束还没能到达终点，返回falsereturn false;}
}