C++搜索算法之广度优先搜索

1.含义
广度优先搜索不同于深度优先搜多，它是一层层进行遍历的，因此需要先入先出的队列而非先入后出的栈进行遍历。由于是按层次进行遍历，广度优先搜索时按照“广”的方向进行遍历的，也常常用来处理最短路径问题。

2.题目一
输入是一个二维整数数组，输出是一个非负整数，表示需要填海造陆的位置数。

本题实际上是求两个岛屿间的最短距离，因此我们可以先通过任意搜索方法找到其中一个岛
屿，然后利用广度优先搜索，查找其与另一个岛屿的最短距离。

vector<int>direction{-1,0,1,0,-1};
//主函数
int shortestBridge(vector<vector<int>>&grid){
    int m=grid.size(),n=grid[0].size();
    queue<pair<int,int>>points;
    //dfs寻找第一个岛屿，并把1全部赋值为2
    bool flipped=false;
    for(int i=0;i<m;++i){
        if(flipped) break;
        for(int j=0;j<n;++j){
            if(grid[i][j]==1){
                dfs(points,grid,m,n,i,j);
                flipped=true;
                break;
            }
        }
    }
    //bfs寻找第二个岛屿，并把过程中经过0的赋值为2
    int x,y;
    int level=0;
    while(!points.empty()){
        ++level;
        int n_points=points.size();
        while(n_points--){
            auto[r,c]=points.front();
            points.pop();
            for(int k=0;k<4;++k){
                x=r+direction[k],y=c+direction[k+1];
                if(x>=0&&y>=0&&x<m&&y<n){
                    if(grid[x][y]==2){
                        continue;
                    }
                    if(grid[x][y]==1){
                        return level;
                    }
                    points.push({x,y});
                    grid[x][y]=2;
                }
            }
        }
    }
    return 0;
}
//辅函数
void dfs(que<pair<int,int>>&points,vector<vetor<int>>&grid,int m,int n,int i,int j){
    if(i<0||j<0||i==m||j==n||grid[i][j]==2){
        return;
    }
    if(grid[i][j]==0){
        points.push({i,j});
        return;
    }
    grid[i]][j]=2;
    dfs(points, grid, m, n, i - 1, j);
    dfs(points, grid, m, n, i + 1, j);
    dfs(points, grid, m, n, i, j - 1);
    dfs(points, grid, m, n, i, j + 1);
}

题目二
给定一个起始字符串和一个终止字符串，以及一个单词表，求是否可以将起始字符串每次改
一个字符，直到改成终止字符串，且所有中间的修改过程表示的字符串都可以在单词表里找到。
若存在，输出需要修改次数最少的所有更改方式。
输入是两个字符串，输出是一个二维字符串数组，表示每种字符串修改方式。

我们可以把起始字符串、终止字符串、以及单词表里所有的字符串想象成节点。若两个字符
串只有一个字符不同，那么它们相连。因为题目需要输出修改次数最少的所有修改方式，因此我
们可以使用广度优先搜索，求得起始节点到终止节点的最短距离。
我们同时还使用了一个小技巧：我们并不是直接从起始节点进行广度优先搜索，直到找到终
止节点为止；而是从起始节点和终止节点分别进行广度优先搜索，每次只延展当前层节点数最少
的那一端，这样我们可以减少搜索的总结点数。举例来说，假设最短距离为 4，如果我们只从一
端搜索 4 层，总遍历节点数最多是 1 + 2 + 4 + 8 + 16 = 31；而如果我们从两端各搜索两层，总遍
历节点数最多只有 2 × (1 + 2 + 4) = 14。
在搜索结束后，我们还需要通过回溯法来重建所有可能的路径。

//主函数
vector<vector<string>>findLadders(string beginWord,string endWord,vector<string>&wordList){
    vector<vector<string>>ans;
    unordered_set<string>>dict;
    for(const auto &w:wordList){
        dict.insert(w);
    }
    if(!dict.count(endWord)){
        return ans;
    }
    dict.erase(beginWord);
    dict.erase(endWord);
    unordered_set<string>q1{beginWord},q2{endWord};
    unordered_map<string,vector<string>>next;
    bool reversed=false,found=false;
    while(!q1.empty()){
        unordered_set<string>q;
        for(const auto&w:q1){  
            string s=w;
            for(size_t i=0;i<s.size();i++){
                char ch=s[i];
                for(int j=0;j<26;j++)
                    s[i]=j+'a';
                    if(q2.count(s)){
                        reversed?next[s].push_back(w):next[w].push_back(s);
                        found=true;
                    }
                    if(dict.count(s)){
                        reversed?next[s].push_back(w):next[w].push_back(s);
                        q.insert(s);
                    }
                }
                s[i]=ch;
            }
        }
        if(found){
            break;
        }
        for(const auto &w:q){
            dict.erase(w);
        }
        if(q.size()<=q2.size()){
            q1=q;
        }
        else{
            reversed=!reversed;
            q1=q2;
            q2=q;
        }
    }
    if(found){
        vector<string>path={beginWord};
        backtracking(beginWord,endWord,next,path,ans);
    }
    return ans;
}
//辅函数
void backtracking(const string&src,const string&dst,unordered_map<string,vector<string>>&next,
        vector<string>&path,vector<vector<string>>&ans){
    if(src===dst)
        ans.push_back(path);
        return;
    }
    for(const auto&s:next[src]){
        path.push_back(s);
        backtracking(s,dst,next,path,ans);
        path.pop_back();
    }
}

Today note
though i cannot achieve this althorighm after having writed it now,i must to think about it
tomorrow->fighting!