第C++回溯算法深度優(yōu)先搜索舉例分析目錄撲克牌全排列員工的重要性圖像渲染被圍繞的區(qū)域島嶼數(shù)量電話號碼的字母組合組合總數(shù)活字印書N皇后

撲克牌全排列

假如有編號為1~3的3張撲克牌和編號為1~3的3個盒子，現(xiàn)在需要將3張牌分別放到3個盒子中去，且每個盒子只能放一張牌，一共有多少種不同的放法。

解題思路：假定按照牌面值從小到大依次嘗試，即將1號牌放入第一個盒子中。按此順序繼續(xù)向后走，放完第三個盒子時，手中的牌也已經(jīng)用完，再繼續(xù)往后則到了盒子的盡頭。此時一種放法已經(jīng)完成了，即這條路走到了盡頭，需要折返，重新回到上一個盒子。這里回到第三個盒子，把第三個盒子中的牌回收，再去嘗試能否放其它的牌。但這時手里只有一張3號牌，所以需要繼續(xù)向后回退，到2號盒子。按照上述步驟依次會產(chǎn)生所有結果。用一個數(shù)組book標記手里是否有這張牌。

Dfs(當前這一步的處理邏輯)

{

1.判斷邊界，是否已經(jīng)一條道走到黑了：向上回退

2.嘗試當下的每一種可能

3.確定一種可能之后，繼續(xù)下一步Dfs(下一步)

}

代碼實現(xiàn)：

voidDFS(vectorintboxs,vectorintbooks,intn,intindex)

if(index=n+1)

for(inti=1;ii++)

coutboxs[i]"";//打印每一種結果

coutendl;

return;

for(inti=1;ii++)

if(books[i]==0)//如果i號牌仍在手上

boxs[index]=i;

books[i]=1;

DFS(boxs,books,n,index+1);

books[i]=0;

}

員工的重要性

問題描述：

給定一個保存員工信息的數(shù)據(jù)結構，它包含了員工唯一的id，重要度和直系下屬的id。比如，員工1是員工2的領導，員工2是員工3的領導。他們相應的重要度為15,10,5。那么員工1的數(shù)據(jù)結構是[1,15,[2]]，員工2的數(shù)據(jù)結構是[2,10,[3]]，員工3的數(shù)據(jù)結構是[3,5,[]]。注意雖然員工3也是員工1的一個下屬，但是由于并不是直系下屬，因此沒有體現(xiàn)在員工1的數(shù)據(jù)結構中。

現(xiàn)在輸入一個公司的所有員工信息，以及單個員工id，返回這個員工和他所有下屬的重要度之和。

解題思路：

邊界：下屬為空

每次先加第一個下屬的重要性

按照相同的操作再去加下屬的第一個下屬的重要性。

代碼實現(xiàn)：

//DefinitionforEmployee.

classEmployee{

public:

intid;

intimportance;

vectorintsubordinates;

classSolution{

public:

intDFS(unordered_mapint,Employee*info,intid)

intcurImpo=info[id]-importance;

for(constautosid:info[id]-subordinates)

curImpo+=DFS(info,sid);

returncurImpo;

intgetImportance(vectorEmployee*employees,intid){

if(employees.empty())

return0;

unordered_mapint,Employee*info;

for(constautoe:employees)

info[e-id]=e;

returnDFS(info,id);

};

圖像渲染

問題描述：

有一幅以二維整數(shù)數(shù)組表示的圖畫，每一個整數(shù)表示該圖畫的像素值大小，數(shù)值在0到65535之間。給你一個坐標(sr,sc)表示圖像渲染開始的像素值（行，列）和一個新的顏色值newColor，讓你重新上色這幅圖像。為了完成上色工作，從初始坐標開始，記錄初始坐標的上下左右四個方向上像素值與初始坐標相同的相連像素點，接著再記錄這四個方向上符合條件的像素點與他們對應四個方向上像素值與初始坐標相同的相連像素點，……，重復該過程。將所有有記錄的像素點的顏色值改為新的顏色值。

最后返回經(jīng)過上色渲染后的圖像。

解題思路:

從所給坐標開始，向上下左右四個方向渲染，只要渲染點的顏色值和原坐標相同，則繼續(xù)向外渲染。邊界：位置是否越界。

這里需要用標記避免重復修改，使時間復雜度不超過O(row*col)

代碼實現(xiàn)：

intnextP[4][2]={{-1,0},{1,0},{0,1},{0,-1}};

classSolution{

public:

voidDFS(vectorvectorintimage,vectorvectorintbook,intsr,intsc,intnewColor,intoldColor,introw,intcol)

image[sr][sc]=newColor;

book[sr][sc]=1;

for(inti=0;ii++)

intcurX=sr+nextP[i][0];

intcurY=sc+nextP[i][1];

//判斷是否越界

if(curX0||curX=row||curY0||curY=col)

continue;

//顏色符合要求且之前沒被渲染過則繼續(xù)渲染

if(image[curX][curY]==oldColorbook[curX][curY]==0)

DFS(image,book,curX,curY,newColor,oldColor,row,col);

vectorvectorintfloodFill(vectorvectorintimage,intsr,intsc,intnewColor){

introw=image.size();

intcol=image[0].size();

intoldColor=image[sr][sc];

vectorvectorintbook(row,vectorint(col,0));

DFS(image,book,sr,sc,newColor,oldColor,row,col);

returnimage;

};

被圍繞的區(qū)域

問題描述：

給你一個mxn的矩陣board，由若干字符‘X'和‘O'，找到所有被‘X'圍繞的區(qū)域，并將這些區(qū)域里所有的‘O'用‘X'填充。

解題思路：從每個邊緣的O開始，只要和邊緣的O連通，則它就沒有被包圍。

1.首先尋找邊上的每一個O，如果沒有，表示所有的O都被包圍。

2.對于邊上的每一個O進行dfs擴散，先把邊上的每一個O用特殊符號標記（除了X和O以外）。把和它相鄰的O都替換為特殊符號，每一個新的位置都做相同的dfs操作。

3.所有擴散結束之后，把特殊符號的位置（和邊界連通）還原為O，原來為O的位置（和邊界不連通）替換為X即可。

代碼實現(xiàn)：

intnextP[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

classSolution{

public:

voidDFS(vectorvectorcharboard,intcurX,intcurY,introw,intcol)

board[curX][curY]='A';

for(inti=0;ii++)

intx=curX+nextP[i][0];

inty=curY+nextP[i][1];

if(x0||x=row

||y0||y=col)

continue;

if(board[x][y]!='A'board[x][y]!='X')

DFS(board,x,y,row,col);

voidsolve(vectorvectorcharboard){

if(board.empty())

return;

introw=board.size();

intcol=board[0].size();

//第一行和最后一行

for(inti=0;icol;i++)

if(board[0][i]=='O')

DFS(board,0,i,row,col);

if(board[row-1][i]=='O')

DFS(board,row-1,i,row,col);

//第一列和最后一列

for(inti=0;irow;i++)

if(board[i][0]=='O')

DFS(board,i,0,row,col);

if(board[i][col-1]=='O')

DFS(board,i,col-1,row,col);

for(inti=1;irow-1;i++)

for(intj=0;jcol;j++)

if(board[i][j]=='A')

board[i][j]='O';

elseif(board[i][j]=='O')

board[i][j]='X';

};

島嶼數(shù)量

問題描述：

給你一個由‘1'（陸地）和‘0'（水）組成的的二維網(wǎng)格，請你計算網(wǎng)格中島嶼的數(shù)量。島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。此外，你可以假設該網(wǎng)格的四條邊均被水包圍。

示例1：

輸入：grid=[[“1”,“1”,“1”,“1”,“0”],[“1”,“1”,“0”,“1”,“0”],[“1”,“1”,“0”,“0”,“0”],[“0”,“0”,“0”,“0”,“0”]]

輸出：1

解題思路：

本題可以采用類似渲染的做法，嘗試以每個點作為渲染的起點，可以渲染的陸地都算作一個島嶼，最后看渲染了多少次，即深度優(yōu)先算法執(zhí)行了多少次，就是島嶼的數(shù)量。

代碼實現(xiàn)：

intnextP[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

classSolution{

public:

voidDFS(vectorvectorchargrid,vectorvectorintbook,intx,inty,introw,intcol)

book[x][y]=1;

for(inti=0;ii++)

intcurX=x+nextP[i][0];

intcurY=y+nextP[i][1];

if(curX0||curX=row||curY0||curY=col)

continue;

if(grid[curX][curY]=='1'book[curX][curY]==0)

DFS(grid,book,curX,curY,row,col);

intnumIslands(vectorvectorchargrid){

if(grid.empty())

return0;

introw=grid.size();

intcol=grid[0].size();

intnum=0;

vectorvectorintbook(row,vectorint(col,0));

for(inti=0;irow;i++)

for(intj=0;jcol;j++)

if(grid[i][j]=='1'book[i][j]==0)

++num;

DFS(grid,book,i,j,row,col);

returnnum;

};

電話號碼的字母組合

問題描述：

給定一個僅包含數(shù)字2-9的字符串，返回所有它能表示的字母組合。答案可以按任意順序返回。給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意1不對應任何字母。

解題思路：

首先使用數(shù)組（也可使用哈希表）存儲每個數(shù)字對應的所有可能的字母，然后進行回溯操作?；厮菟惴ㄓ糜趯ふ宜械目尚薪?，如果發(fā)現(xiàn)一個解不可行，則會舍棄不可行的解。在這道題中，由于每個數(shù)字對應的每個字母都可能進入字母組合，因此不存在不可行的解，直接窮舉所有的解即可。

代碼實現(xiàn)：

stringmapString[]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

classSolution{

public:

voidDFS(stringdigits,vectorstringresult,stringcurStr,intcurDepth)

//邊界，找到一種組合，放入數(shù)組中，結束此路徑，向上回溯

if(curDepth==digits.size())

if(!curStr.empty())

result.push_back(curStr);

return;

//找到當前字符映射在mapString種的位置

intcurMapIndex=digits[curDepth]-'0';

stringcurMap=mapString[curMapIndex];

//遍歷每一種可能

for(constautoch:curMap)

DFS(digits,result,curStr+ch,curDepth+1);

vectorstringletterCombinations(stringdigits){

vectorstringresult;

DFS(digits,result,"",0);

returnresult;

};

組合總數(shù)

問題描述：

給你一個無重復元素的整數(shù)數(shù)組candidates和一個目標整數(shù)target，找出candidates中可以使數(shù)字和為目標數(shù)target的所有不同組合，并以列表形式返回。你可以按任意順序返回這些組合。

candidates中的同一個數(shù)字可以無限制重復被選取。如果至少一個數(shù)字的被選數(shù)量不同，則兩種組合是不同的。

對于給定的輸入，保證和為target的不同組合數(shù)少于150個。

輸入：candidates=[2,3,6,7],target=7

輸出：[[2,2,3],[7]]

解題思路：

此題相加的元素可以重復，所以去下一個元素的位置可以從當前位置開始，DFS+回溯。為了保證組合不重復（順序不同，元素相同，也算重復），不再從當前位置向前看。

1.從第一個元素開始相加

2.讓局部和繼續(xù)累加候選的剩余值

3.局部和等于目標值，保存組合，向上回退，尋找其它組合

代碼實現(xiàn)：

classSolution{

public:

voidDFS(vectorintcandidates,vectorvectorintresult,vectorintcurCand,intprePos,intcurSum,inttarget)

if(curSum=target)

if(curSum==target)

result.push_back(curCand);

return;

for(inti=prePos;icandidates.size();i++)

if(candidates[i]=target)

curCand.push_back(candidates[i]);

DFS(candidates,result,curCand,i,curSum+candidates[i],target);

//回溯

curCand.pop_back();

vectorvectorintcombinationSum(vectorintcandidates,inttarget){

vectorvectorintresult;

vectorintcurCand;

DFS(candidates,result,curCand,0,0,target);

returnresult;

};

活字印書

問題描述：

你有一套活字字模tiles，其中每個字模上都刻有一個字母tiles[i]。返回你可以印出的非空字母序列的數(shù)目。

注意：本題中，每個活字字模只能使用一次。

示例1：

輸入：“AAB”

輸出：8

解釋：可能的序列為“A”,“B”,“AA”,“AB”,“BA”,“AAB”,“ABA”,“BAA”。

解題思路：

此題組合的長度不唯一，最小組合長度為1，最大組合長度為tiles的長度。按照題意tiles中每一個位置的字符在組合中只能出現(xiàn)一次，所以可以用一個標記輔助。當組合新的組合時，可以與tiles種的每一個位置組合，但是如果當前位置已經(jīng)在當前組合中出現(xiàn)過，則跳過。雖然此題種每一個位置的字符在組合中只能出現(xiàn)一次，但是tiles中可能有相同的字符，所以需要考慮重復的組合。而用unordered_set可以天然去重。

DFS+回溯：

1.當前組合不為空，則插入set中

2.繼續(xù)給當前組合拼接新的組合，嘗試拼接tiles每一個位置的字符

3.如果當前位置已經(jīng)在組合中出現(xiàn)過，返回到2，否則標記當前位置，繼續(xù)拼接更長的組合

4.回溯，嘗試組合其它位置，返回2

當所有位置都已經(jīng)使用過時，當前遞歸就結束了，繼續(xù)向上層DFS回退

最終返回set大小即為組合數(shù)目

代碼實現(xiàn)：

classSolution{

public:

voidDFS(stringtiles,vectorintbook,stringcurStr,unordered_setstringtotolaString)

if(!curStr.empty())

totolaString.insert(curStr);

for(inti=0;itiles.size();i++)

//當前字符已用過，跳過

if(book[i]==1)

continue;

book[i]=1;

DFS(tiles,book,curStr+tiles[i],totolaString);

book[i]=0;

intnumTilePossibilities(stringtiles){

vectorintbook(tiles.size(),0);

unordered_setstringtotolaString;

DFS(tiles,book,"",totolaString);

returntotolaString.size();

};

N皇后

問題描述：

n皇后問題研究的是如何將n個皇后放置在n×n的棋盤上，并且使皇后彼此之間不能相互攻擊。

給你一個整數(shù)n，返回所有不同的n皇后問題的解決方案。

每一種解法包含一個不同的n皇后問題的棋子放置方案，該方案中‘Q'和‘.'分別代表了皇后和空位。

解題思路：

DFS+回溯

從第一行開始放置皇后，每確定一個位置，判斷是否會沖突（是否在同一列、同一斜線，已經(jīng)不可能在同一行）

同一列：縱坐標相同

同一斜線：坐標差或坐標和相同。

當前行位置確定后，繼續(xù)確定下一行的位置。

回退，嘗試其他行的其它位置。

代碼實現(xiàn)：

classSolution{

public:

boolisValidPos(vectorpairint,intcurRet,introw,intcol)

for(pairint,intpos:curRet)

if(pos.second==col||pos.fir