但其實，這題也可以用BFS 解！而且實作非常簡單，舉這個例子是想讓大家看看BFS 也可以應用在沒有明顯graph 結構的問題上，我們會在第四個範例中解釋 ...
TechBridge技術共筆部落格
Menu
Home
About
Tags
Archives
RSS
SignIn
前言
身在大CS時代，有越來越多人投入刷題的行列，在眼花撩亂的題海中，要想有效率地刷題，就需要掌握題目解法中，可以在許多地方應用的觀念，才能以簡禦繁。
Huli寫的程式解題新手入門注意事項講得很好，寫題目是為了學會解題的思考方法，確保自己掌握重要的資料結構跟演算法。
這也是為什麼我想要寫這系列的文章，把多個散落在各處的題目銜接起來，以後看到相似的問題就可以舉一反三，而不是去背各題目的解法。
舉例來說，之前遇過一題電話面試，問到的題目是：
Input:vectorholidays,intpto
holidays表示平日或假日，例如0000011表示前面5天是平日，後面2天是假日。
pto表示最多可以放幾天假。
Output:計算在可以用完pto的情況下，最久可以放多長的假。
範例：holidays={0,0,0,0,0,1,1},pto=2,output=4
因為可以放{0,0,0,1,1,1,1}
基本上因為之前有寫過SlidingWindow的pattern，所以這題很快就寫出來了，也順利進到下一關，所以大家不需要追求把題目都刷完，而是掌握好重要的基礎，接下來就是應用這些基礎就可以面對很多變化題（當然還是會有一些解法很巧妙的題目，但其實大部分公司不會硬出巧妙題）。
放上程式碼給大家參考：
#include
#include
usingnamespacestd;
intlongest_holidays(constvector&holidays,intpto){
intlongestHoliday=-1,windowStart=0;
for(intwindowEnd=0;windowEndholidays={0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,1,1,1};
intlongest_holiday=longest_holidays(holidays,9);
cout<queue;//storeallnodeswhicharewaitingtobeprocessed
step=0;//numberofstepsneeededfromroottocurrentnode
//initialize
addroottoqueue;
//BFS
while(queueisnotempty){
step=step+1;
//iteratethenodeswhicharealreadyinthequeue
intsize=q.size();
for(inti=0;iqueue;//storeallnodeswhicharewaitingtobeprocessed
Setvisited;//storeallthenodesthatwe'vevisited
step=0;//numberofstepsneeededfromroottocurrentnode
//initialize
addroottoqueue;
addroottovisited;
//BFS
while(queueisnotempty){
step=step+1;
//iteratethenodeswhicharealreadyinthequeue
intsize=queue.size();
for(inti=0;i>&rooms){
//Checkcornercases
intm=rooms.size();
if(m<1){return;}
intn=rooms[0].size();
if(n<1){return;}
//PrepareforBFS
intGATE=0,WALL=-1,ROOM=numeric_limits::max();
queue>q;
vector>dirs{{0,-1},{-1,0},{0,1},{1,0}};
//Putallgatesintoqueue
for(inti=0;i=0;--sz){
paircur=q.front();
q.pop();
if(rooms[cur.first][cur.second]==ROOM){
rooms[cur.first][cur.second]=steps;
}
if(rooms[cur.first][cur.second]!=WALL){
//Traverseneighbor
for(inti=0;i&cur,constint&m,constint&n){
returncur.first>=0&&cur.first=0&&cur.second>&grid){
intm=grid.size(),n=m?grid[0].size():0,islands=0;
//走過矩陣的所有element，只要遇到島，就把島都消滅(即'1'->'0')
for(inti=0;i>&grid,constint&m,constint&n,constint&i,constint&j){
if(grid[i][j]=='0')return;
grid[i][j]='0';
if(i-1>=0){dfs(grid,m,n,i-1,j);}
if(i+1=0){dfs(grid,m,n,i,j-1);}
if(j+1>&grid){
intm=grid.size(),n=m?grid[0].size():0,islands=0,offsets[]={0,1,0,-1,0};
for(inti=0;i>todo;
todo.push({i,j});
while(!todo.empty()){
pairp=todo.front();
todo.pop();
for(intk=0;k<4;k++){
intr=p.first+offsets[k],c=p.second+offsets[k+1];
if(r>=0&&r=0&&c1000,9000,0100,0900,0010,0090,0001,0009->...->...->target
所以就開始有可以使用BFS的影子出現。
換句話說，因為看到有起點、要求最短距離，所以想了"走一步"是什麼意思？然後想到就是把其中一個數字+1或-1。
接著就可以再延伸，發現這就是一個從0000開始，然後假設deadends是已經visit過所以不能再走，的一個BFS問題。
Breadth-FirstSearch解法
classSolution{
public:
intopenLock(vector&deadends,stringtarget){
//PrepareforBFS
//因為不能走到deadends裡面的排列，所以我們直接放進visited，這樣做BFS時就不會考慮這些路線
unordered_setvisited(deadends.begin(),deadends.end());
arraydigit={'0','1','2','3','4','5','6','7','8','9'};
queuetodo;
//假設0000沒有在visited(也就是deadends裡沒有)中，我們才需要開始尋找
if(!visited.count("0000")){
todo.push("0000");
visited.insert("0000");
}
//StartBFS
intsteps=-1;
while(!todo.empty()){
++steps;
for(intsz=todo.size()-1;sz>=0;--sz){
stringcur=todo.front();
todo.pop();
//Checkifit'starget
if(cur==target){
returnsteps;
}
//Gothroughneighbors
//如何找到對的neighbor也是這題比較tricky的地方之一
for(inti=0;i<4;++i){
for(intj=-1;j<=1;j+=2){
stringneighbor=cur;
//Wraparoundindextopreventout-of-bounderror
neighbor[i]=digit[(neighbor[i]-'0'+j+10)%10];
if(!visited.count(neighbor)){
todo.push(neighbor);
visited.insert(neighbor);
}
}
}
}
}
return-1;
}
};
寫完這題，如果你是BFS新手，應該會覺得頗好玩，因為這題的鄰居找法跟之前有明顯matrix結構的情況不太一樣，而是變成在另一個抽象的搜索空間中做BFS。
Breadth-FirstSearch的第四個範例-Leetcode#279-PerfectSquares
題目
暴力解
暴力法很直覺，反正就每種組合都試試看就對了，例如若要看12至少要由幾個perfectsuqarenumber組成，那就看"1至少要幾個+11至少要幾個"、"2至少要幾個+10至少要幾個"...依此類推，直到比較過所有可能的拆分方法，就知道最少要幾個，實作如下：
classSolution{
public:
intnumSquares(intn){
if(isPerfectSquare(n)){
return1;
}
intres=n;
for(inti=1;i<=n/2;++i){
intcomb=numSquares(i)+numSquares(n-i);
if(combvisited;
queuetodo;
todo.push(0);
visited.insert(0);
//StartBFS
intsteps=0;
while(!todo.empty()){
++steps;
for(intsz=todo.size()-1;sz>=0;--sz){
//Retrievecurrentint
intcur=todo.front();
todo.pop();
for(intj=1;jn){break;}
else{
if(!visited.count(sum)){
todo.push(sum);
visited.insert(sum);
}
}
}
}
}
returnsteps;
}
};
Breadth-FirstSearch的第五個範例-Leetcode#1284-MinimumNumberofFlipstoConvertBinaryMatrixtoZeroMatrix
題目
這一題是我在某一週的Leetcodecontest寫到的，因為當時我正好寫完上面四個BFS的範例題，對BFS的pattern很有感覺，所以這題很快就寫出來了。
Breadth-FirstSearch解法
因為概念上跟第三個範例有點像，都是在自己想像中的搜索空間中進行BFS，所以這題的想法我就不贅述了，基本上就是把整個matrix的狀態當作node，每翻一次就是走一步，就可以用BFS解決了，附上程式碼：
classSolution{
public:
intminFlips(vector>&mat){
//Checkcornercases
intm=mat.size();
intn=m?mat[0].size():0;
if(m<1orn<1){return-1;}
//PrepareforBFS
set>>visited;
queue>>q;
q.push(mat);
visited.insert(mat);
intsteps=0;
while(!q.empty()){
for(intsz=q.size()-1;sz>=0;--sz){
vector>cur=q.front();
q.pop();
//已經成功翻成全部都是0
if(allZero(cur)){
returnsteps;
}
for(intr=0;r>&mat,int&m,int&n,int&r,int&c){
//翻鄰居
if(r-1>=0){mat[r-1][c]=(mat[r-1][c]==1)?0:1;}
if(r+1=0){mat[r][c-1]=(mat[r][c-1]==1)?0:1;}
if(c+1>&mat){
for(inti=0;i
