搜索专项---最短路模型

---

文章目录 迷宫问题武士风度的牛抓住那头牛

---

一、迷宫问题OJ链接

        本题思路:只需要记录各个点是有哪个点走过来的，就能递推得出路径。记录前驱假设从 1,1 这个点向下走到了2, 1，则将2,1这个点的前驱记为1,1。这样，将整张地图 bfs 后，各个点的前驱就被记录了下来。输出路径：经过 bfs ，各个点的前驱已经被记录下来，我们只需要从终点开始，依次找当前节点的前驱，就能一直找到起点，从而得到一条路径。当然，这条路径是终点到起点的路径，倒序输出即为起点到终点的路径。如果 bfs 是从终点开始，则讲过上述步骤，得到的就是从起点到终点的路径，不用倒序输出。

#include <bits/stdc++.h> #define x first #define y second typedef std::pair<int,int> PII; constexpr int N=1010; int n; int g[N][N]; bool st[N][N]; PII pre[N][N];//储存当前位置的前驱位置 std::queue<PII> q; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; void bfs(int ax,int ay) { q.push({ax,ay}); st[ax][ay]=true; while(!q.empty()){ PII t=q.front(); q.pop(); for(int i=0;i<4;i++){ int a=t.x+dx[i],b=t.y+dy[i]; if(a<0||a>=n||b<0||b>=n) continue; if(g[a][b]) continue; if(!st[a][b]){ q.push({a,b}); pre[a][b]=t; st[a][b]=true; } } } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr);std::cout.tie(nullptr); std::cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) std::cin>>g[i][j]; bfs(n-1,n-1);//从终点位置进行遍历 PII end(0,0); while (true) { std::cout<<end.x<<" "<<end.y<<std::endl; if (end.x == n - 1 && end.y == n - 1) break; end = pre[end.x][end.y]; } } 二、武士风度的牛OJ链接

   本题题解: 从牛的起点，进行 bfs 即可。根据题意，牛走的是日字， 八个点。因此，dx, dy 和之前的四个点是不同的。可以得出：dx = [-2, -1, 1, 2, 2, 1, -1, -2]，dy = [1, 2, 2, 1, -1, -2, -2, -1] 具体的：找到牛的起点，从起点开始进行 bfs向八个方向进行探索，判断这八个点是否合法：不越界和牛能走。对于合法的点，记录从起点走过来的距离，也就是上个点的距离+1。将合法的点放入队列。如果在 bfs过程中遇到了终点（干草） ，则返回答案。

#include <bits/stdc++.h> #define x first #define y second typedef std::pair<int,int> PII; constexpr int N=2000; int n,m; char g[N][N]; int dist[N][N]; std::queue<PII> q; int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1}; int bfs(int ax,int ay) { memset(dist,-1,sizeof dist); dist[ax][ay]=0; q.push({ax,ay}); while(!q.empty()){ PII t=q.front(); q.pop(); for(int i=0;i<8;i++){ int a=t.x+dx[i],b=t.y+dy[i]; if(a<0||a>=n||b<0||b>=m) continue; if(g[a][b]=='*') continue; if(dist[a][b]!=-1) continue; if(g[a][b]=='H') return dist[t.x][t.y]+1; dist[a][b]=dist[t.x][t.y]+1; q.push({a,b}); } } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr);std::cout.tie(nullptr); std::cin>>m>>n; for(int i=0;i<n;i++) std::cin>>g[i]; int ax,ay; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(g[i][j]=='K'){ ax=i; ay=j; } std::cout<<bfs(ax,ay)<<std::endl; return 0; } 三、抓住那头牛OJ链接

       本题思路: 这道题是一个一维的找最短路径的问题，无论+1，-1，* 2 花费都是1分钟，即权值相同， 所以才能用BFS去找最短路。假设当前点为t , 目标点为k出队扩展循环判断 1、如果t-1小于0了，那就不能走-1的方法 2、如果t+1 大于了N(10的5次方+10 ），就不能走+1的方法。 3、如果t * 2大于了N，也就不能走* 2的方法了。当然三个判断都应该加上此点是否被走过的条件，如果满足条件，就把其入队，出队时判断t是否等于k，如果相等就return距离。那么为什么N要取的比K大一点呢，因为先减1再乘2扩大会比先乘再减一缩小更快的接近K，1、当k为偶数，假设为100，当前点为51，那么减一再乘更快，2、当k为奇数，假设为99，当前点为50，那么先乘再减一时更快一点的。所以N要取的比K大一点，当超过N的时候就不会有这样的区别，一定是先减再乘可以更快的接近K。

#include <bits/stdc++.h> constexpr int N=1e5+10; int n,k; int dist[N]; std::queue<int> q; int bfs() { q.push(n); dist[n]=0; while(!q.empty()){ auto t=q.front(); q.pop(); if(t==k) return dist[k]; if(t-1>=0&&dist[t-1]==-1){ q.push(t-1); dist[t-1]=dist[t]+1; } if(t+1<=N&&dist[t+1]==-1){ q.push(t+1); dist[t+1]=dist[t]+1; } if(t*2<=N&&dist[t*2]==-1){ q.push(t*2); dist[t*2]=dist[t]+1; } } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr);std::cout.tie(nullptr); memset(dist,-1,sizeof dist); std::cin>>n>>k; std::cout<<bfs()<<std::endl; return 0; }