leetcode 2812. 找出最安全路径 中等

给你一个下标从0开始、大小为n x n的二维矩阵grid其中(r, c)表示如果grid[r][c] 1则表示一个存在小偷的单元格如果grid[r][c] 0则表示一个空单元格你最开始位于单元格(0, 0)。在一步移动中你可以移动到矩阵中的任一相邻单元格包括存在小偷的单元格。矩阵中路径的安全系数定义为从路径中任一单元格到矩阵中任一小偷所在单元格的最小曼哈顿距离。返回所有通向单元格(n - 1, n - 1)的路径中的最大安全系数。单元格(r, c)的某个相邻单元格是指在矩阵中存在的(r, c 1)、(r, c - 1)、(r 1, c)和(r - 1, c)之一。两个单元格(a, b)和(x, y)之间的曼哈顿距离等于| a - x | | b - y |其中|val|表示val的绝对值。示例 1输入grid [[1,0,0],[0,0,0],[0,0,1]]输出0解释从 (0, 0) 到 (n - 1, n - 1) 的每条路径都经过存在小偷的单元格 (0, 0) 和 (n - 1, n - 1) 。示例 2输入grid [[0,0,1],[0,0,0],[0,0,0]]输出2解释上图所示路径的安全系数为 2 - 该路径上距离小偷所在单元格02最近的单元格是00。它们之间的曼哈顿距离为 | 0 - 0 | | 0 - 2 | 2 。 可以证明不存在安全系数更高的其他路径。示例 3输入grid [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]输出2解释上图所示路径的安全系数为 2 - 该路径上距离小偷所在单元格03最近的单元格是12。它们之间的曼哈顿距离为 | 0 - 1 | | 3 - 2 | 2 。 - 该路径上距离小偷所在单元格30最近的单元格是32。它们之间的曼哈顿距离为 | 3 - 3 | | 0 - 2 | 2 。 可以证明不存在安全系数更高的其他路径。提示1 grid.length n 400grid[i].length ngrid[i][j]为0或1grid至少存在一个小偷分析题目要求找出从起点 (0,0) 到终点 (n−1,n−1) 的路径中的最大安全系数。安全系数定义为从起点到终点路径上的任意单元格到任意有小偷的单元格的最小曼哈顿距离。由于路径必然包含起点和终点因此如果这两个单元格中任意一个存在小偷最小曼哈顿距离即为 0此时最大安全系数也为 0。另外矩阵中至少有一个小偷无论小偷位于何处起点到终点路径上任意单元格到小偷的曼哈顿距离都不会超过 n。最大化路径的安全系数等价于最大化路径上所有单元格到小偷的最小曼哈顿距离的最小值。如果事先计算出每个单元格到最近小偷的曼哈顿距离可以用一个 n×n 的二维数组记录那么原问题就转换为在二维矩阵中从起点 (0,0) 走到终点 (n−1,n−1)找出一条路径最大化路径上节点值的最小值。首先使用多源 BFS 来求出所有单元格到小偷单元格的最小曼哈顿距离将所有小偷的位置作为源点同时入队进行广度优先搜索用二维数组 dis 记录结果其中 dis[x][y] 表示位置 (x,y) 到最近小偷的曼哈顿距离。接下来可以从起点开始进行深度优先搜索或广度优先搜索只允许经过值大于等于 limit 的节点搜索结束后判断是否能抵达终点。因为随着 limit 减小原本可行的路径依然可行所以答案具有单调性。于是我们可以用二分查找来寻找满足条件的最大 limit记为 ans满足当 limit≤ans 时可以从起点走到终点当 limitans 时则无法到达终点。另外路径必然包含起点和终点因此二分查找的上界不会超过 min(dis[0][0],dis[n−1][n−1])。在区间 [0,min(dis[0][0],dis[n−1][n−1])] 上进行二分查找即可得到最终的答案。class Solution { public: int maximumSafenessFactor(vectorvectorint grid) { int ngrid.size(),dist[n][n]; if(grid[0][0]1||grid[n-1][n-1]1)return 0; queuepairint,intque; int x[]{-1,1,0,0},y[]{0,0,-1,1}; for(int i0;in;i) { for(int j0;jn;j) { dist[i][j]INT_MAX; if(grid[i][j]1) que.push({i,j}),dist[i][j]0; } } int left0,rightINT_MIN,mid; while(!que.empty()) { int xxque.front().first,yyque.front().second;que.pop(); rightmax(dist[xx][yy]1,right); for(int i0;i4;i) { int temp_xxxxx[i],temp_yyyyy[i]; if(temp_xx0||temp_xxn||temp_yy0||temp_yyn)continue; if(dist[xx][yy]1dist[temp_xx][temp_yy]) dist[temp_xx][temp_yy]dist[xx][yy]1,que.push({temp_xx,temp_yy}); } } int ans0; while(leftright) { int f0;mid(leftright)/2; queuepairint,inttemp_que; mappairint,int,intmp; if(dist[0][0]mid)temp_que.push({0,0}); while(!temp_que.empty()!f) { int xxtemp_que.front().first,yytemp_que.front().second;temp_que.pop(); // printf(xx%d yy%d dis%d mid%d\n,xx,yy,dist[xx][yy],mid); for(int i0;i4!f;i) { int temp_xxxxx[i],temp_yyyyy[i]; if(temp_xx0||temp_xxn||temp_yy0||temp_yyn)continue; // printf(temp_xx%d temp_yy%d dis%d mid%d\n,temp_xx,temp_yy,dist[temp_xx][temp_yy],mid); if(dist[temp_xx][temp_yy]midmp[{temp_xx,temp_yy}]0) { if(temp_xxn-1temp_yyn-1)f1; temp_que.push({temp_xx,temp_yy});mp[{temp_xx,temp_yy}]1; } } } if(f)ansmax(ans,mid),leftmid1; else rightmid; // printf(f%d ans%d left%d right%d\n,f,ans,left,right); } return ans; } };