给一个nxn的二维矩阵grid
- grid[r][c] = 1 ，表示一个存在小偷的单元格
- grid[r][c] = 0 ，则表示一个空单元格
每个单元格的安全系数为离所有小偷曼哈顿距离的最小值
（1,1）到（n,n）路径的安全系数为所有单元格安全系数最小值
求一条最大安全系数路径
1. 多源广度优先 + 记忆化搜索 + 二分查找
class Solution {
public:
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int maximumSafenessFactor(vector<vector<int>>& grid) {
//尽量避开小偷
//这里需要计算路径每一个点的安全系数，将每一个点与所有小偷位置做计算？
//直接通过小偷，预计算每一个点的安全系数
int res = 0;//经过小偷的路径安全系数为0
int n = grid.size();
queue<int> q;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==1){
grid[i][j] = 0;//安全系数为0
q.push(i*n+j);//小偷坐标入队
}
else grid[i][j] = INT_MAX;//没有计算的可通行坐标
}
}
while(!q.empty()){
int cur = q.front(); q.pop();
int x = cur/n; int y = cur%n;
for(int i=0;i<4;i++){
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if(nx<0||nx==n||ny<0||ny==n||grid[nx][ny]!=INT_MAX) continue;//跳过非法节点
grid[nx][ny] = grid[x][y] + 1;//安全系数增加
q.push(nx*n+ny);
}
}
//上面通过计算得到了所有点的安全系数，接着找最优路径
bool vis[n][n];
function<bool(int, int, int)> f = [&](int x,int y,int w) -> bool {//判断是否存在对应安全系数路径
if(grid[x][y]<w) return false;//该路径不符
if(x==n-1&&y==n-1) return true;//到达目的
vis[x][y] = true; //做选择
for(int i=0;i<4;i++){//遍历四个方向
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if(nx<0||nx==n||ny<0||ny==n||vis[nx][ny]) continue;//跳过非法节点和已访问节点
if(f(nx,ny,w)) return true;
}
//vis[x][y] = false; //撤销选择，这里不进行撤销，作为dp表示经过该点的路径无效
return false;
};
int left = 0; int right = n-1;//安全系数的最小值和最大值
while(left<right){
memset(vis,false,sizeof(vis));
int mid = (left+right+1)/2;
if(f(0,0,mid)) left = mid;
else right = mid-1;
}
return left;
}
};