1.含义
宽度优先搜索与深度优先搜索较多不同，由于是分层次进行遍历，所以需要在先进先出的队列而不是先进先出的堆栈中进行遍历。 由于分层次地进行遍历，所以在宽度优先搜索中是在“宽”方向上进行遍历，也经常用于应对最短路径问题。2.题目一
输入是二维整数数组，输出是一个非负整数，表示需要填海的位置数。
主题实际上是求出两个岛之间的最短距离，所以首先可以通过任意的检索方法找到其中一个岛
利用岛屿和面积优先搜索，寻找与其他岛屿的最短距离。
vctorintdirection {-1，0，1，0，-1}； //主函数intshortestbridge (vectorvectorintgrid ) { int m=grid.size，n=grid[0].size )； queuepairint，intpoints； //dfs寻找第一个岛，将1全部代入2 bool flipped=false； for(intI=0； im； I )集成电路(if )断开； for(intj=0； jn； j () if ) grid[I][j]==1) DFS ) points，grid，m，n，I，j )； flipped=true； 布雷克； } } } //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(intk=0； k4； { x=r direction[k]，y=c direction[k 1]； if(x=0y=0xmyn ) if ) grid[x][y]==2) { continue； }if(grid[x][y]==1) { return level； }points.push () x，y )； grid[x][y]=2； } } }返回0； //辅助函数voidDFS(quepairint，intpoints，vectorvetorintgrid，int m，int n，int i，int j ) if(I0|||J0|I==m|J (if 返回； }网格[ 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 )； } 题目二
给出开始字符串、结束字符串和单词列表，提示是否可以每次更改开始字符串
一个字符，更改为结束字符串，直到中间更改过程中表示的所有字符串都显示在单词表中。
如果存在，则是输出所需修改次数最少的所有更改方法。
输入两个字符串，输出是二维字符串数组，表示如何修改每个字符串。
可以将开始字符串、结束字符串、单词表中的所有字符串视为节点。 2个字符时
如果只有一个文字不同，它们就会连接起来。 因为主题需要输出修改次数最少的所有修改方法，所以我
使用宽度优先搜索，可以求出从开始节点到结束节点的最短距离。
我们还在用小技巧。 我们从第一个节点直接进行广度优先搜索，并不是找到最后
直到节点停止； 相反，从起点节点和终点节点分别进行宽度优先搜索，每次扩展为当前分层节点数最多
少的那一端，这样我们可以减少搜索的总结点数。举例来说，假设最短距离为 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!