企业官网建设流程全解析

给你一个下标从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： - 该路径上距离小偷所在单元格（0，2）最近的单元格是（0，0）。它们之间的曼哈顿距离为 | 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： - 该路径上距离小偷所在单元格（0，3）最近的单元格是（1，2）。它们之间的曼哈顿距离为 | 0 - 1 | + | 3 - 2 | = 2 。 - 该路径上距离小偷所在单元格（3，0）最近的单元格是（3，2）。它们之间的曼哈顿距离为 | 3 - 3 | + | 0 - 2 | = 2 。 可以证明，不存在安全系数更高的其他路径。

提示：

• 1 <= grid.length == n <= 400
• grid[i].length == n
• grid[i][j]为0或1
• grid至少存在一个小偷

分析：题目要求找出从起点 (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 时，可以从起点走到终点；
当 limit>ans 时，则无法到达终点。
另外，路径必然包含起点和终点，因此二分查找的上界不会超过 min(dis[0][0],dis[n−1][n−1])。在区间 [0,min(dis[0][0],dis[n−1][n−1])] 上进行二分查找，即可得到最终的答案。

class Solution { public: int maximumSafenessFactor(vector<vector<int>>& grid) { int n=grid.size(),dist[n][n]; if(grid[0][0]==1||grid[n-1][n-1]==1)return 0; queue<pair<int,int>>que; int x[]={-1,1,0,0},y[]={0,0,-1,1}; for(int i=0;i<n;++i) { for(int j=0;j<n;++j) { dist[i][j]=INT_MAX; if(grid[i][j]==1) que.push({i,j}),dist[i][j]=0; } } int left=0,right=INT_MIN,mid; while(!que.empty()) { int xx=que.front().first,yy=que.front().second;que.pop(); right=max(dist[xx][yy]+1,right); for(int i=0;i<4;++i) { int temp_xx=xx+x[i],temp_yy=yy+y[i]; if(temp_xx<0||temp_xx>=n||temp_yy<0||temp_yy>=n)continue; if(dist[xx][yy]+1<dist[temp_xx][temp_yy]) dist[temp_xx][temp_yy]=dist[xx][yy]+1,que.push({temp_xx,temp_yy}); } } int ans=0; while(left<right) { int f=0;mid=(left+right)/2; queue<pair<int,int>>temp_que; map<pair<int,int>,int>mp; if(dist[0][0]>=mid)temp_que.push({0,0}); while(!temp_que.empty()&&!f) { int xx=temp_que.front().first,yy=temp_que.front().second;temp_que.pop(); // printf("xx=%d yy=%d dis=%d mid=%d\n",xx,yy,dist[xx][yy],mid); for(int i=0;i<4&&!f;++i) { int temp_xx=xx+x[i],temp_yy=yy+y[i]; if(temp_xx<0||temp_xx>=n||temp_yy<0||temp_yy>=n)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]>=mid&&mp[{temp_xx,temp_yy}]==0) { if(temp_xx==n-1&&temp_yy==n-1)f=1; temp_que.push({temp_xx,temp_yy});mp[{temp_xx,temp_yy}]=1; } } } if(f)ans=max(ans,mid),left=mid+1; else right=mid; // printf("f=%d ans=%d left=%d right=%d\n",f,ans,left,right); } return ans; } };