---

文章目錄

• 迷宮問題
• 武士風度的牛
• 抓住那頭牛

---

一、迷宮問題OJ鏈接

??????? 本題思路:只需要記錄各個點是有哪個點走過來的，就能遞推得出路徑。記錄前驅(qū)假設(shè)從 1,1 這個點向下走到了2, 1，則將2,1這個點的前驅(qū)記為1,1。這樣，將整張地圖 bfs 后，各個點的前驅(qū)就被記錄了下來。輸出路徑：經(jīng)過 bfs ，各個點的前驅(qū)已經(jīng)被記錄下來，我們只需要從終點開始，依次找當前節(jié)點的前驅(qū)，就能一直找到起點，從而得到一條路徑。當然，這條路徑是終點到起點的路徑，倒序輸出即為起點到終點的路徑。如果 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];//儲存當前位置的前驅(qū)位置
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 即可。根據(jù)題意，牛走的是日字， 八個點。因此，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分鐘，即權(quán)值相同， 所以才能用BFS去找最短路。假設(shè)當前點為t , 目標點為k出隊擴展循環(huán)判斷 1、如果t-1小于0了，那就不能走-1的方法 2、如果t+1 大于了N(10的5次方+10 ），就不能走+1的方法。 3、如果t * 2大于了N，也就不能走* 2的方法了。當然三個判斷都應(yīng)該加上此點是否被走過的條件，如果滿足條件，就把其入隊，出隊時判斷t是否等于k，如果相等就return距離。那么為什么N要取的比K大一點呢，因為先減1再乘2擴大會比先乘再減一縮小更快的接近K，1、當k為偶數(shù)，假設(shè)為100，當前點為51，那么減一再乘更快，2、當k為奇數(shù)，假設(shè)為99，當前點為50，那么先乘再減一時更快一點的。所以N要取的比K大一點，當超過N的時候就不會有這樣的區(qū)別，一定是先減再乘可以更快的接近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;
}