题目描述：
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一：
0 表示草地。1 表示着火的格子。2 表示一座墙，你跟火都不能通过这个格子。
一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟，你可以移动到 相邻 的草地格子。每次你移动 之后 ，着火的格子会扩散到所有不是墙的 相邻 格子。
请你返回你在初始位置可以停留的 最多 分钟数，且停留完这段时间后你还能安全到达安全屋。如果无法实现，请你返回 -1 。如果不管你在初始位置停留多久，你 总是 能到达安全屋，请你返回 109 。
注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。
如果两个格子有共同边，那么它们为 相邻 格子。
数据范围：
$2\le m, n \le 300, 4\le m \times n \le 2 \times 10^4$ .
题解：
复杂度只支持 $n\log n$ 的做法。
可以先试用多源bfs得到每个点被火覆盖的时间。
多源bfs和单源类似，直接把所有的起点入队，每次第一次遍历到一个未访问过的节点时就是最短的。也可以加上判断是不是最短路，判断有几条最短路经过了该点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| queue<int> q;
int bfs()
{
while(!q.empty())
{
int out = q.front(); q.pop();
if(times[out] == m) return out;
for(int i = head[out]; i; i = edge[i].next)
{
int v = edge[i].v;
if(dis[v] == 0 || dis[v] == dis[out] + 1)
{
dis[v] = dis[out] + 1;
times[v] += times[out];
if(!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
return -1;
}
|
多源bfs得到每个点被火覆盖的时间之后，需要从起点走到终点。发现具有二分单调性，停留的时间越短，能够通过，越多，越不能通过。
因此可以二分停留的时间，然后使用bfs check能否从起点走到终点。假设停留了 $mid$ 分钟，那么花费了 $t$ 到达 $v$ ，则如果 $grid[v] <= t + 1$ 则说明火已经覆盖到 $v$ ， $v$ 不能扩展。但是终点是例外的，终点如果恰好被火覆盖是能逃跑的。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<int> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
bool check(int mid, vector<vector<int>> &grid)
{
if (grid[0][0] <= mid)
return false;
int n = grid.size(), m = grid[0].size();
queue<pair<int, int>> q;
vector<vector<bool>> vis(n, vector<bool>(m, false));
q.push({0, mid});
vis[0][0] = true;
while (q.size())
{
auto out = q.front();
q.pop();
int x = out.first / m;
int y = out.first % m;
int dis = out.second;
if (x == n - 1 && y == m - 1)
return true;
for (int i = 0; i < 4; ++i)
{
int newx = x + dx[i];
int newy = y + dy[i];
if (newx == n - 1 && newy == m - 1 && grid[newx][newy] >= dis + 1)
return true;
if (newx < 0 || newx >= n || newy < 0 || newy >= m || grid[newx][newy] <= 0 ||
grid[newx][newy] <= dis + 1 || vis[newx][newy])
continue;
q.push({newx * m + newy, dis + 1});
vis[newx][newy] = true;
}
}
return false;
}
int maximumMinutes(vector<vector<int>> &grid)
{
int n = grid.size(), m = grid[0].size();
queue<pair<int, int>> q;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (grid[i][j] == 2)
grid[i][j] = -2;
if (grid[i][j] == 0)
grid[i][j] = INF;
if (grid[i][j] == 1)
{
grid[i][j] = 0;
q.push({i, j});
}
}
}
while (q.size())
{
auto out = q.front();
q.pop();
for (int i = 0; i < 4; ++i)
{
int newx = out.first + dx[i];
int newy = out.second + dy[i];
if (newx < 0 || newx >= n || newy < 0 || newy >= m || grid[newx][newy] <= 0 || grid[newx][newy] != INF)
continue;
grid[newx][newy] = min(grid[newx][newy], grid[out.first][out.second] + 1);
q.push({newx, newy});
}
}
int l = 0, r = m * n, ans = -1;
while (l <= r)
{
int mid = (l + r) >> 1;
if (check(mid, grid))
{
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
return ans == m * n ? 1e9 : ans;
}
};
|