展示型网站案例,电影网站模板html,海南seo排名,网店怎么开步骤目录 1.题目2.思路3.代码实现#xff08;Java#xff09; 1.题目
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid #xff0c;它表示一个网格图。每个格子为下面 3 个值之一#xff1a;
0 表示草地。1 表示着火的格子。2 表示一座墙#xff0c;你跟火都不能通过… 目录 1.题目2.思路3.代码实现Java 1.题目
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid 它表示一个网格图。每个格子为下面 3 个值之一
0 表示草地。1 表示着火的格子。2 表示一座墙你跟火都不能通过这个格子。
一开始你在最左上角的格子 (0, 0) 你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟你可以移动到 相邻 的草地格子。每次你移动 之后 着火的格子会扩散到所有不是墙的相邻格子。
请你返回你在初始位置可以停留的最多分钟数且停留完这段时间后你还能安全到达安全屋。如果无法实现请你返回 -1。如果不管你在初始位置停留多久你总是能到达安全屋请你返回 109。
注意如果你到达安全屋后火马上到了安全屋这视为你能够安全到达安全屋。如果两个格子有共同边那么它们为相邻格子。
示例 1 输入grid [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]] 输出3 解释上图展示了你在初始位置停留 3 分钟后的情形。 你仍然可以安全到达安全屋。 停留超过 3 分钟会让你无法安全到达安全屋。
示例 2
输入grid [[0,0,0,0],[0,1,2,0],[0,2,0,0]] 输出-1 解释上图展示了你马上开始朝安全屋移动的情形。 火会蔓延到你可以移动的所有格子所以无法安全到达安全屋。 所以返回 -1 。
示例 3 输入grid [[0,0,0],[2,2,0],[1,2,0]] 输出1000000000 解释上图展示了初始网格图。 注意由于火被墙围了起来所以无论如何你都能安全到达安全屋。 所以返回 109 。
提示 m grid.length n grid[i].length 2 m, n 300 4 m * n 2 * 104 grid[i][j] 是 0 1 或者 2 。 grid[0][0] grid[m - 1][n - 1] 0
2.思路
1BFS 二分搜索 思路参考本题官方题解。
相关题目 LeetCode_多源 BFS_中等_994.腐烂的橘子
3.代码实现Java
//思路1————BFS 二分搜索
class Solution {final int INF 1000000000;int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int m;int n;public int maximumMinutes(int[][] grid) {m grid.length;n grid[0].length;//保存每个格子着火的时间int[][] fireTime new int[m][n];for (int i 0; i m; i) {Arrays.fill(fireTime[i], INF);}bfs(grid, fireTime);//使用二分搜索查找在初始位置可以停留的最多分钟数int res -1;int left 0;int right m * n;while (left right) {int mid left (right - left) / 2;if (check(fireTime, grid, mid)) {left mid 1;res mid;} else {right mid - 1;}}return res m * n ? INF : res;}//判断起点停留的时间为 stayTime 时能否到达安全屋private boolean check(int[][] fireTime, int[][] grid, int stayTime) {boolean[][] visited new boolean[m][n];Queueint[] queue new ArrayDeque();queue.offer(new int[]{0, 0, stayTime});visited[0][0] true;while (!queue.isEmpty()) {int[] index queue.poll();int ci index[0];int cj index[1];int time index[2];for (int[] dir : dirs) {int ni ci dir[0];int nj cj dir[1];if (ni 0 ni m nj 0 nj n) {if (visited[ni][nj] || grid[ni][nj] 2) {continue;}//到达安全屋if (ni m - 1 nj n - 1) {return fireTime[ni][nj] time 1;}//火未到达当前位置if (fireTime[ni][nj] time 1) {queue.offer(new int[]{ni, nj, time 1});visited[ni][nj] true;}}}}return false;}//多源 bfspublic void bfs(int[][] grid, int[][] fireTime) {Queueint[] queue new ArrayDeque();//将目前着火的格子坐标放入到队列中for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {queue.offer(new int[]{i, j});fireTime[i][j] 0;}}}int time 1;while (!queue.isEmpty()) {int size queue.size();for (int i 0; i size; i) {int[] index queue.poll();int ci index[0];int cj index[1];for (int[] dir : dirs) {int ni ci dir[0];int nj cj dir[1];if (ni 0 ni m nj 0 nj n) {if (grid[ni][nj] 2 || fireTime[ni][nj] ! INF) {continue;}queue.offer(new int[]{ni, nj});fireTime[ni][nj] time;}}}time;}}
}
