leetcode357- 2812. 找出最安全路径

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

多源BFS

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

// 以所有小偷为起点进行多源 bfs
        memset(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尽可能地大。

枚举安全系数

//直接从大到小枚举
        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) ;
    }