搜索专项---最短路模型
文章目录
- 迷宫问题
- 武士风度的牛
- 抓住那头牛
一、迷宫问题OJ链接
本题思路:只需要记录各个点是有哪个点走过来的，就能递推得出路径。记录前驱假设从 1,1 这个点向下走到了2, 1，则将2,1这个点的前驱记为1,1。这样，将整张地图 bfs 后，各个点的前驱就被记录了下来。输出路径：经过 bfs ，各个点的前驱已经被记录下来，我们只需要从终点开始，依次找当前节点的前驱，就能一直找到起点，从而得到一条路径。当然，这条路径是终点到起点的路径，倒序输出即为起点到终点的路径。如果 bfs 是从终点开始，则讲过上述步骤，得到的就是从起点到终点的路径，不用倒序输出。
#include <bits/stdc++.h>#define x first
#define y secondtypedef 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 secondtypedef 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;
}