leetcode357- 2812. 找出最安全路径

这个题比较经典，可以用多个算法来求解，分别给出各个算法的求解方法，主要是分为第一部分的多源BFS求每个位置的距离和第二部分求(0,0)到(n-1,n-1)的最短路径（可以用多种方法求）

多源BFS

首先是要求得每个点距离最近的小偷所在位置的距离长度：
暴力枚举每个小偷所在位置，更新所有点到该小偷位置的距离，数据量为400，假设每个位置都有小偷，小偷数量达到400*400，再加上枚举每个位置，最后的复杂度为O(400 * 400 * 400 * 400)，即O(n^4)会超时；
多源BFS求距离：多源BFS

// 以所有小偷为起点进行多源 bfsmemset(dis, -1, sizeof(dis));for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (grid[i][j] == 1) {q.push(pii(i, j));dis[i][j] = 0;}while (!q.empty()) {pii p = q.front(); q.pop();int i = p.first, j = p.second;for (int k = 0; k < 4; k++) {int ii = i + dir[k][0], jj = j + dir[k][1];if (ii < 0 || jj < 0 || ii >= n || jj >= m || dis[ii][jj] >= 0) continue;q.push(pii(ii, jj));dis[ii][jj] = dis[i][j] + 1;}}

求最短路径

枚举安全系数判断是否可行

枚举答案看是否存在满足答案的路径。
这个思路采用逆向思维方式，不是枚举最短路径判断安全系数，而是枚举安全系数判断对应的最短路径是否存在，也是分为两部分，一部分是如何枚举安全系数，另一部分是如何判断只经过安全系数为lim并且连通起点到终点的路径是否存在。
枚举路径中安全系数（经过的格子的最小值）可以是哪些，相当于枚举只经过安全系数为lim的路径，路径中经过的格子安全系数全都大于等于lim，能否从起点到达终点；然后让这个lim尽可能地大。

枚举安全系数

1. 可以直接从最大的开始枚举，找到一个符合条件的就可以结束了，O(n)

//直接从大到小枚举for(int i=min(dis[0][0],dis[n-1][m-1]);i>=0;i--){if(check(i)) return i;}

2. 二分枚举, O(logn) 【最小值最大或者是最大值最小问题】

//二分int l=0,r=min(dis[0][0],dis[n-1][m-1]);while(l<r){int mid=(l+r+1)>>1;if(check(mid)) l=mid;else r=mid-1;}

路径是否存在

判断路径上的安全系数为lim，也就是之前求出来的所有节点的值大于等于lim的连接起点到终点的路径是否存在，有多种方法，bfs，dfs，并查集，只要判断起点和终点连通就行。

1. BFS
   bfs检查时间，每个位置处遍历一次，复杂度为O(n^2)

    //通过一次bfs，检查能否只经过安全系数大于等于lim的格子，从左上角走到右下角bool check(int lim){q.push({0,0});memset(visited, 0, sizeof(visited));visited[0][0]=true;while(!q.empty()){pii p = q.front(); q.pop();int i = p.first, j = p.second;for (int k = 0; k < 4; k++) {int ii = i + dir[k][0], jj = j + dir[k][1];if (ii < 0 || jj < 0 || ii >= n || jj >= m || dis[ii][jj]<lim ||visited[ii][jj]) continue;q.push(pii(ii, jj));visited[ii][jj]=true;}}return visited[n-1][n-1];}

2. DFS
   深搜不行，因为涉及到回溯，导致每个节点可能访问多次，导致深搜的时间复杂度无法控制在O(n^2)内，会超时。

3. 并查集判断(0,0)和(n-1,n-1)是否连通

   int find(int x){if(p[x]==x) return x;return p[x]=find(p[x]);}//并差集判断bool check(int lim){//初始化并查集每个元素是自己，将二维的数组拉成一维的int x=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){p[x]=x;x++; }}//将每个节点与周围节点合并for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(dis[i][j]<lim) continue;int a=find(i*n+j);for (int k = 0; k < 4; k++) {int ii = i + dir[k][0], jj = j + dir[k][1];if (ii < 0 || jj < 0 || ii >= n || jj >= m || dis[ii][jj]<lim ) continue;int b =find(ii*n+jj);if(a!=b)  p[b]=a;  //合并}}}return find(0)==find(n*n-1) ;}