BFS基本模闆

在部落格上看見别人總結的bfs基本模闆感覺挺好的就自己稍做修改儲存了下來

#include <bits/stdc++.h>
using namespace std;
#define N 10000000//迷宮的規模
type start,aim;//type為某種資料類型
//start初始位置，aim目标位置
struct node{
int  x;
int step;
};
//記錄兩種狀态
//1.記錄該步的狀态
//2.步數
bool vis[N];
//标記該種狀态是否被走過
queue<node> q;
//廣搜隊列
void bfs()
{

    while(!q.empty())
    {
        if(q.front().x==aim)
        {
            return;
        }
        node tmp;
        //tmp用于暫時儲存狀态
        int X=q.front().x;
        //一維隻有X
        //多元要從多重次元記錄
        int Step=q.front().step;
        q.pop();
        //進行減一的操作
        //廣度試探
        if(X>=1&&!vis[X-1])
            //要保證減1後有意義,是以要X >= 1
            //其中之一的試探條件
        {
        tmp.x=X-1;//進行操作
        //到達新的狀态
        tmp.step=Step+1;
        vis[X-1]=1;
        //記錄已經到達過的位置
        //記錄該狀态已經試探過了
        q.push(tmp);
        }
        //已經到達的位置不能重複到達
        //進行加一的操作
        if(X<aim&&!vis[X+1])
            //總的來說試探條件有三個
            //1.在邊界之内
            //2.還未走過
            //3.該處沒有”牆“
        {
        tmp.x=X+1;
        tmp.step=Step+1;
        vis[X+1]=1;
        q.push(tmp);
        }
        //進行乘兩倍的操作
        if(X<aim&&!vis[2*X])
        {
            tmp.x=2*X;
            tmp.step=Step+1;
            vis[2*X]=1;
            q.push(tmp);
        }
   }
}
int main()
{
    while(cin>>start>>aim)//初始化迷宮
    {
        memset(vis,0,sizeof(vis));
        //初始化記錄狀态的數組
        while(!q.empty())q.pop();
        //確定在進行操作之前隊列為空
        node ST;
        ST.x=start;
        ST.step=0;
        q.push(ST);
        //将根節點進隊
        //同時開始廣度優先搜尋
        bfs();
        //可能在此處會有一個較為複雜的輸出函數
        cout<<q.front().step<<endl;
    }
    return 0;
}