网站的功能,韩国搜索引擎排名,外贸网络推广方法,购物建设网站文章目录
迷宫问题武士风度的牛抓住那头牛 一、迷宫问题OJ链接 本题思路:只需要记录各个点是有哪个点走过来的#xff0c;就能递推得出路径。记录前驱假设从 1,1 这个点向下走到了2, 1#xff0c;则将2,1这个点的前驱记为1,1。这样#xff0c;将整张地图 bfs 后#xff0c… 文章目录
迷宫问题武士风度的牛抓住那头牛 一、迷宫问题OJ链接 本题思路:只需要记录各个点是有哪个点走过来的就能递推得出路径。记录前驱假设从 1,1 这个点向下走到了2, 1则将2,1这个点的前驱记为1,1。这样将整张地图 bfs 后各个点的前驱就被记录了下来。输出路径经过 bfs 各个点的前驱已经被记录下来我们只需要从终点开始依次找当前节点的前驱就能一直找到起点从而得到一条路径。当然这条路径是终点到起点的路径倒序输出即为起点到终点的路径。如果 bfs 是从终点开始则讲过上述步骤得到的就是从起点到终点的路径不用倒序输出。
#include bits/stdc.h#define x first
#define y secondtypedef std::pairint,int PII;constexpr int N1010;int n;
int g[N][N];
bool st[N][N];
PII pre[N][N];//储存当前位置的前驱位置
std::queuePII 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 tq.front();q.pop();for(int i0;i4;i){int at.xdx[i],bt.ydy[i];if(a0||an||b0||bn) 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::cinn;for(int i0;in;i)for(int j0;jn;j)std::cing[i][j];bfs(n-1,n-1);//从终点位置进行遍历PII end(0,0);while (true){std::coutend.x end.ystd::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::pairint,int PII;constexpr int N2000;int n,m;
char g[N][N];
int dist[N][N];
std::queuePII 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 tq.front();q.pop();for(int i0;i8;i){int at.xdx[i],bt.ydy[i];if(a0||an||b0||bm) 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::cinmn;for(int i0;in;i) std::cing[i];int ax,ay;for(int i0;in;i)for(int j0;jm;j)if(g[i][j]K){axi;ayj;}std::coutbfs(ax,ay)std::endl;return 0;
}
三、抓住那头牛OJ链接 本题思路: 这道题是一个一维的找最短路径的问题无论1-1* 2 花费都是1分钟即权值相同 所以才能用BFS去找最短路。假设当前点为t , 目标点为k出队扩展循环判断 1、如果t-1小于0了那就不能走-1的方法 2、如果t1 大于了N(10的5次方10 就不能走1的方法。 3、如果t * 2大于了N也就不能走* 2的方法了。当然三个判断都应该加上此点是否被走过的条件如果满足条件就把其入队出队时判断t是否等于k如果相等就return距离。那么为什么N要取的比K大一点呢因为先减1再乘2扩大会比先乘再减一缩小更快的接近K1、当k为偶数假设为100当前点为51那么减一再乘更快2、当k为奇数假设为99当前点为50那么先乘再减一时更快一点的。所以N要取的比K大一点当超过N的时候就不会有这样的区别一定是先减再乘可以更快的接近K。
#include bits/stdc.hconstexpr int N1e510;int n,k;
int dist[N];
std::queueint q;int bfs()
{q.push(n);dist[n]0;while(!q.empty()){auto tq.front();q.pop();if(tk) return dist[k];if(t-10dist[t-1]-1){q.push(t-1);dist[t-1]dist[t]1;}if(t1Ndist[t1]-1){q.push(t1);dist[t1]dist[t]1;}if(t*2Ndist[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::cinnk;std::coutbfs()std::endl;return 0;
}
