bfs

BFS
1. 多源bfs
2.最小步數模型
- 1.魔闆
- 2.八數位問題
3.雙端隊列廣搜
4.雙向廣搜
5.A*算法

BFS

bfs是搜尋算法裡面最基礎的算法，對于隊首的點，每次搜尋其周圍所有的點，然後将其入隊。隊列裡面的點具有兩個特性：

（1）單調性，即隊列的元素是遞增的（可以相等）

（2）不重複，不會有相同的點

1. 多源bfs

一般的問題是求單源bfs，單源的意思就是一個起點，那麼多源就是多個起點。

BFS的使用（acwing提高課之搜尋）BFS1. 多源bfs2.最小步數模型3.雙端隊列廣搜4.雙向廣搜5.A*算法

題意就是：周遊每個點，找到距離目前點最近的值為‘1’的點，記錄他們之間的距離。

很明顯，這是一個最短路問題，而且邊權為1，滿足這兩個條件，可以考慮bfs了。但是有一個問題，通常使用bfs的時候，隻有一個起點，這題每個點都是起點，那麼怎麼做？

實際上，将所有值為‘1’的點作為一個整體，都當成起點即可。因為值為1的點到最近的值為1的點就是其本身。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int N=1010;
typedef pair<int,int>PII;

char g[N][N];
int dist[N][N];

int n,m;

void bfs()
{
    int dx[4]={-1,0,1,0};
    int dy[4]={0,1,0,-1};
    queue<PII>q;
    memset(dist,-1,sizeof dist);
    //首先将所有值為1的點入隊
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(g[i][j]=='1')
            {
                dist[i][j]=0;
                q.push({i,j});
            }
        }
    while(!q.empty())
    {
       PII t=q.front();
       q.pop();
       int a=t.first;
       int b=t.second;
       for(int i=0;i<4;i++)
       {
            int x=a+dx[i];
            int y=b+dy[i];
            if(x<1||y<1||x>n||y>m)continue;
            if(dist[x][y]!=-1)continue;
            else
            {
                dist[x][y]=dist[a][b]+1;  //不需要去min，因為第一次周遊到的一定是最小的，初始的起點每個點都是走一圈，每次都是如此。所有對于每個點都是一樣的
                q.push({x,y});
            }
       }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
    bfs();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
           cout<<dist[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

2.最小步數模型

最小步數模型常見的有八數位問題。

這裡記錄模闆和八數位。

核心思想：普通的最小步數隻需要記錄點的坐标，也就是普通意義上的‘點’。然而可以更加抽象‘點’。将一個狀态表示為一個點。以點為面，以面為點。八數位問題就是如此。

1.魔闆

BFS的使用（acwing提高課之搜尋）BFS1. 多源bfs2.最小步數模型3.雙端隊列廣搜4.雙向廣搜5.A*算法

思路：将每個數組的狀态當作一個點，然後進行一個“擴充”，這裡的擴充就是三個基本操作。（對比普通bfs，擴充點就是搜尋可以達到的周圍鄰點）

#include<iostream>
#include<cstring>
#include<queue>
#include<unordered_map>
#include<algorithm>
using namespace std;

unordered_map<string,pair<char,string>>pre;  //記錄目前的狀态是由哪個狀态轉移過來的。并且記錄上一步轉移過來使用的是哪種方案
unordered_map<string,int>dist;  //記錄從起始狀态轉移到目前狀态用了多少步數
char g[2][4];


void set(string state)
{
    for (int i = 0; i < 4; i ++ ) g[0][i] = state[i];
    for (int i = 7, j = 0; j < 4; i --, j ++ ) g[1][j] = state[i];
}

string get()
{
    string res;
    for (int i = 0; i < 4; i ++ ) res += g[0][i];
    for (int i = 3; i >= 0; i -- ) res += g[1][i];
    return res;
}

string move0(string state)
{
    set(state);
    for (int i = 0; i < 4; i ++ ) swap(g[0][i], g[1][i]);
    return get();
}

string move1(string state)
{
    set(state);
    int v0 = g[0][3], v1 = g[1][3];
    for (int i = 3; i > 0; i -- )
    {
        g[0][i] = g[0][i - 1];
        g[1][i] = g[1][i - 1];
    }
    g[0][0] = v0, g[1][0] = v1;
    return get();
}

string move2(string state)
{
    set(state);
    int v = g[0][1];
    g[0][1] = g[1][1];
    g[1][1] = g[1][2];
    g[1][2] = g[0][2];
    g[0][2] = v;
    return get();
}



int bfs(string start,string end)
{
    //start通過廣搜得到end
    if(start==end)return 0;
    queue<string>q;
    q.push(start);
    dist[start]=0;
    while(!q.empty())
    {
        auto t=q.front();
        q.pop();
        
        //t有三種轉移方式
        string m[3];
        m[0]=move0(t);
        m[1]=move1(t);
        m[2]=move2(t);
        
        for(int i=0;i<3;i++)
        {
            if(!dist.count(m[i]))  //目前的狀态沒有出現過
            {
                dist[m[i]]=dist[t]+1;
                pre[m[i]]={'A'+i,t};
                q.push(m[i]);
                if(m[i]==end)return dist[m[i]];
            }
        }
    }
    return -1;
}
int main()
{
    string start,end;
    for(int i=0;i<8;i++)
    {
        int x;
        cin>>x;
        end+=char(x+'0');
    }
    for(int i=0;i<8;i++)start+=char(i+'1');
    int step=bfs(start,end);
    cout<<step<<endl;
    //cout<<start<<" "<<end<<endl;
    //下面輸出路徑
    string res="";
    while(end!=start)
    {
        res+=pre[end].first;
        end=pre[end].second;
    }
    reverse(res.begin(),res.end());
    if(step>0)
        cout<<res<<endl;
    return 0;
}

2.八數位問題

3.雙端隊列廣搜

BFS的使用（acwing提高課之搜尋）BFS1. 多源bfs2.最小步數模型3.雙端隊列廣搜4.雙向廣搜5.A*算法

題意：從左上角到右下角，保證電路連通的情況下，最少扭轉多少次線路。

假設兩個點直接不需要扭轉直接的線路，則兩點的距離設定為0，否則為1.那麼就變成了一個求最短路問題.

雙端隊列主要解決圖中邊的權值隻有0或者1的最短路問題

每次從隊頭取出元素，并進行拓展其他元素時、

若拓展某一進制素的邊權是0，則将該元素插入到隊頭

若拓展某一進制素的邊權是1，則将該元素插入到隊尾

#include<iostream>
#include<cstring>
#include<algorithm>
#include<deque>
using namespace std;

const int N=510;
typedef pair<int,int>PII;
#define x first
#define y second
char g[N][N];
int dist[N][N];
bool st[N][N];

int T;
int n,m;

//定義搜尋周圍的方向，左上，右上，左下，右下
int dx[4]={-1,-1,1,1};
int dy[4]={-1,1,1,-1};
int ix[4]={-1,-1,0,0};
int iy[4]={-1,0,0,-1};
int bfs()
{
    memset(dist,0x3f,sizeof dist);
    memset(st,false,sizeof st);
    deque<PII>q;
    dist[0][0]=0;
    q.push_back({0,0});
    char cs[5]={'\\','/','\\','/'};
    while(!q.empty())
    {
        PII t=q.front();
        q.pop_front();
        st[t.x][t.y] = true;

        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 > m) continue;

            int ca = t.x + ix[i], cb = t.y + iy[i];
            int d = dist[t.x][t.y] + (g[ca][cb] != cs[i]);

            if (d < dist[a][b])
            {
                dist[a][b] = d;

                if (g[ca][cb] != cs[i]) q.push_back({a, b});
                else q.push_front({a, b});
            }
        }
    }
    return dist[n][m];
}

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cin>>g[i][j];
        int ans=bfs();
        if(m+n&1)cout<<"NO SOLUTION\n";
        else cout<<ans<<endl;
    }
    return 0;
}

4.雙向廣搜

bfs問題當規模很大的時候，不妨從兩端向中間搜尋。這樣複雜度會降低.但是代碼難寫一點

BFS的使用（acwing提高課之搜尋）BFS1. 多源bfs2.最小步數模型3.雙端隊列廣搜4.雙向廣搜5.A*算法

題意：給兩個字元串，分别是起始狀态和結束狀态，然後給定幾個變換規則。要求找到最少變化次數。

發現，如果單詞bfs，那麼時間複雜度會逾時，是以嘗試使用雙向bfs。

思路：

兩個字元串都同時作為起始狀态，隻要保證在搜尋過程中，兩者有一個狀态是一樣的，那麼傳回兩者路徑之和

。

關鍵在于每次擴充的時候，都需要将那一層所有的狀态去和另一邊去比較。否則答案不正确。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<queue>
using namespace std;


const int N=6;

string A,B;
string a[N],b[N];
int n;

int expand(queue<string>&q,unordered_map<string,int>&da,unordered_map<string,int>&db,string a[N],string b[N])
{
    int d=da[q.front()];
    while(q.size()&&d==da[q.front()])
    {
        string t=q.front();
        q.pop();
        for(int i=0;i<n;i++)
            for(int j=0;j<t.size();j++)
            {
                if(t.substr(j,a[i].size())==a[i])
                {
                    string r=t.substr(0,j)+b[i]+t.substr(j+a[i].size());
                    if(db.count(r))return da[t]+1+db[r];
                    if(da.count(r))continue;
                    da[r]=da[t]+1;
                    q.push(r);
                }
            }
    }
    return 10000;
}
int bfs()
{
    if(A==B)return 0;
    queue<string>qa,qb;
    unordered_map<string,int>da,db;
    da[A]=0,db[B]=0;
    qa.push(A),qb.push(B);
    int step=0;
    while(qa.size()&&qb.size())
    {
        int t;
        if(qa.size()>qb.size())
            t=expand(qb,db,da,b,a);
        else
            t=expand(qa,da,db,a,b);
        if(t<=10)return t;
        if(++step==10)return -1;
    }
    return -1;
}

int main()
{
    cin>>A>>B;
    while(cin>>a[n]>>b[n])n++;
    int t=bfs();
    if(t==-1)cout<<"NO ANSWER!";
    else cout<<t;
    return 0;
}

5.A*算法

BFS的使用（acwing提高課之搜尋）BFS1. 多源bfs2.最小步數模型3.雙端隊列廣搜4.雙向廣搜5.A*算法

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;

typedef pair<int,string>PIS;
string start,x;

int f(string m)  //計算目前狀态到終點的狀态的估計距離
{
    int dt=0;
    for(int i=0;i<9;i++)
    {
        if(m[i]!='x')
        {
            int t=m[i]-'1';  //實際位置
            dt=dt+abs(i/3-t/3)+abs(i%3-t%3);
        }
    }
    return dt;
}

string bfs()
{
    string end="12345678x";
    unordered_map<string,int>dist;
    unordered_map<string,pair<string,int>>last;
    priority_queue<PIS,vector<PIS>,greater<PIS>>heap;
    dist[start]=0;
    heap.push({f(start),start});  //加入起點，記錄目前的點和總距離
    char oper[]="udlr";
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,-1,1};
    while(heap.size())
    {
        auto t =heap.top();
        heap.pop();
        
        string state=t.second;
        if(state==end)break;  //找到最近距離
        
        int x,y;
        for(int i=0;i<9;i++)
            if(state[i]=='x')
            {
                x=i/3,y=i%3;
                break;
            }
        
        string init=state;
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a<0||b<0||a>2||b>2)continue;
            swap(state[a*3+b],state[x*3+y]);
            if(!dist.count(state)||dist[state]>dist[init]+1)
            {
                dist[state]=dist[init]+1;
                heap.push({f(state)+dist[state],state});
                last[state]={init,oper[i]};
            }
            state=init;
        }
    }
    
    string ans;
    while(end!=start)
    {
        ans+=last[end].second;
        end=last[end].first;
    }
    reverse(ans.begin(),ans.end());
    return ans;    
}
int main()
{
    
    char c;
    while(cin>>c)
    {
        start+=c;
        if(c!='x')x+=c;
    }
    //逆序對個數為奇數不能到達終點（12345678x）
    //終點是沒有逆序對的。九宮格裡面，x左右交換不改變逆序對數量，上下交換改變偶數對，是以如果起始
    //狀态是奇數個逆序對，則無法到達終點。
    int cnt=0;
    for(int i=0;i<8;i++)
        for(int j=i+1;j<8;j++)
            if(x[i]>x[j])cnt++;
    if(cnt%2)cout<<"unsolvable";
    else cout<<bfs();
    return 0;
}

先記錄到這，，，

BFS的使用（acwing提高課之搜尋）BFS1. 多源bfs2.最小步數模型3.雙端隊列廣搜4.雙向廣搜5.A*算法

bfs

BFS

1. 多源bfs

2.最小步數模型

1.魔闆

2.八數位問題

3.雙端隊列廣搜

4.雙向廣搜

5.A*算法

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希