网站开发朋友圈广告,免费网页空间,淘宝电脑版,wordpress速度慢解决方法这个题比较经典#xff0c;可以用多个算法来求解#xff0c;分别给出各个算法的求解方法#xff0c;主要是分为第一部分的多源BFS求每个位置的距离和第二部分求(0,0)到(n-1,n-1)的最短路径#xff08;可以用多种方法求#xff09; 目录 多源BFS求最短路径枚举安全系数判断…这个题比较经典可以用多个算法来求解分别给出各个算法的求解方法主要是分为第一部分的多源BFS求每个位置的距离和第二部分求(0,0)到(n-1,n-1)的最短路径可以用多种方法求 目录 多源BFS求最短路径枚举安全系数判断是否可行枚举安全系数路径是否存在 多源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尽可能地大。
枚举安全系数
可以直接从最大的开始枚举找到一个符合条件的就可以结束了O(n)
//直接从大到小枚举for(int imin(dis[0][0],dis[n-1][m-1]);i0;i--){if(check(i)) return i;}二分枚举, O(logn) 【最小值最大或者是最大值最小问题】
//二分int l0,rmin(dis[0][0],dis[n-1][m-1]);while(lr){int mid(lr1)1;if(check(mid)) lmid;else rmid-1;}路径是否存在
判断路径上的安全系数为lim也就是之前求出来的所有节点的值大于等于lim的连接起点到终点的路径是否存在有多种方法bfsdfs并查集只要判断起点和终点连通就行。
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];}DFS 深搜不行因为涉及到回溯导致每个节点可能访问多次导致深搜的时间复杂度无法控制在O(n^2)内会超时。 并查集判断(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 x0;for(int i0;in;i){for(int j0;jm;j){p[x]x;x; }}//将每个节点与周围节点合并for(int i0;in;i){for(int j0;jm;j){if(dis[i][j]lim) continue;int afind(i*nj);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*njj);if(a!b) p[b]a; //合并}}}return find(0)find(n*n-1) ;}
