首頁 > 軟體

C++回溯演演算法深度優先搜尋舉例分析

2022-03-24 19:00:34

撲克牌全排列

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

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

Dfs(當前這一步的處理邏輯)
{
1. 判斷邊界，是否已經一條道走到黑了：向上回退
2. 嘗試當下的每一種可能
3. 確定一種可能之後，繼續下一步 Dfs(下一步)
}

程式碼實現：

void DFS(vector<int>& boxs, vector<int>& books, int n, int index)
{
	if (index >= n + 1)
	{
		for (int i = 1; i <= n; i++)
			cout << boxs[i] << " "; //列印每一種結果
		cout << endl;
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (books[i] == 0) //如果i號牌仍在手上
		{
			boxs[index] = i;
			books[i] = 1;
			DFS(boxs, books, n, index + 1);
			books[i] = 0;
		}
	}
}

員工的重要性

問題描述：

給定一個儲存員工資訊的資料結構，它包含了員工 唯一的 id ，重要度 和 直系下屬的 id 。 比如，員工 1 是員工 2 的領導，員工 2 是員工 3 的領導。他們相應的重要度為 15 , 10 , 5 。那麼員工 1 的資料結構是 [1, 15, [2]] ，員工 2的 資料結構是 [2, 10, [3]] ，員工 3 的資料結構是 [3, 5, []] 。注意雖然員工 3 也是員工 1 的一個下屬，但是由於 並不是直系 下屬，因此沒有體現在員工 1 的資料結構中。

現在輸入一個公司的所有員工資訊，以及單個員工 id ，返回這個員工和他所有下屬的重要度之和。

解題思路：

邊界：下屬為空

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

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

程式碼實現：

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/

class Solution {
public:
    int DFS(unordered_map<int, Employee*>& info, int id)
    {
        int curImpo = info[id]->importance;
        for(const auto& sid : info[id]->subordinates)
        {
            curImpo += DFS(info, sid);
        }

        return curImpo;
    }

    int getImportance(vector<Employee*> employees, int id) {
        if(employees.empty())
            return 0;
        unordered_map<int, Employee*> info;
        for(const auto& e : employees)
        {
            info[e->id] = e;
        }

        return DFS(info, id);
    }
};

影象渲染

問題描述：

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

最後返回經過上色渲染後的影象。

解題思路:

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

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

程式碼實現：

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

class Solution {
public:
    void DFS(vector<vector<int>>& image, vector<vector<int>>& book, int sr, int sc, int newColor, int oldColor, int row, int col)
    {
        image[sr][sc] = newColor;
        book[sr][sc] = 1;
        for(int i = 0; i < 4; i++)
        {
            int curX = sr + nextP[i][0];
            int curY = sc + nextP[i][1];

            //判斷是否越界
            if(curX < 0 || curX >= row || curY < 0 || curY >= col)
                continue;
            //顏色符合要求且之前沒被渲染過則繼續渲染
            if(image[curX][curY] == oldColor && book[curX][curY] == 0)
            {
                DFS(image, book, curX, curY, newColor, oldColor, row, col);
            }
        }
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int row = image.size();
        int col = image[0].size();
        int oldColor = image[sr][sc];
        vector<vector<int>> book(row, vector<int>(col, 0));

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

        return image;
    }
};

被圍繞的區域

問題描述：

給你一個 m x n 的矩陣 board ，由若干字元 ‘X' 和 ‘O' ，找到所有被 ‘X' 圍繞的區域，並將這些區域裡所有的 ‘O' 用 ‘X' 填充。

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

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

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

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

程式碼實現：

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

class Solution {
public:
    void DFS(vector<vector<char>>& board, int curX, int curY, int row, int col)
    {
        board[curX][curY] = 'A';
        for(int i = 0; i < 4; i++)
        {
            int x = curX + nextP[i][0];
            int y = curY + nextP[i][1];

            if(x < 0 || x >= row
               ||y < 0 || y >= col)
                continue;

            if(board[x][y] != 'A' && board[x][y] != 'X')
                DFS(board, x, y, row, col);
        }
    }

    void solve(vector<vector<char>>& board) {
        if(board.empty())
            return;
        int row = board.size();
        int col = board[0].size();

        //第一行和最後一行
        for(int i = 0; i < col; 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(int i = 0; i < row; 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(int i = 1; i < row-1; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(board[i][j] == 'A')
                    board[i][j] = 'O';
                else if(board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }
};

島嶼數量

問題描述：

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

範例 1：

輸入：grid = [ [「1」,「1」,「1」,「1」,「0」], [「1」,「1」,「0」,「1」,「0」], [「1」,「1」,「0」,「0」,「0」], [「0」,「0」,「0」,「0」,「0」] ]

輸出：1

解題思路：

本題可以採用類似渲染的做法，嘗試以每個點作為渲染的起點，可以渲染的陸地都算作一個島嶼，最後看渲染了多少次，即深度優先演演算法執行了多少次，就是島嶼的數量。

程式碼實現：

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

class Solution {
public:
    void DFS(vector<vector<char>>& grid, vector<vector<int>>& book, int x, int y, int row, int col)
    {
        book[x][y] = 1;
        for(int i = 0; i < 4; i++)
        {
            int curX = x + nextP[i][0];
            int curY = y + nextP[i][1];

            if(curX < 0 || curX >= row || curY < 0 || curY >= col)
                continue;
            
            if(grid[curX][curY] == '1' && book[curX][curY] == 0)
                DFS(grid, book, curX, curY, row, col);
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty())
            return 0;
        int row = grid.size();
        int col = grid[0].size();
        int num = 0;
        vector<vector<int>> book(row, vector<int>(col, 0));
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(grid[i][j] == '1' && book[i][j] == 0)
                {
                    ++num;
                    DFS(grid, book, i, j, row, col);
                }
            }
        }

        return num;
    }
};

電話號碼的字母組合

問題描述：

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

解題思路：

首先使用陣列（也可使用雜湊表）儲存每個數位對應的所有可能的字母，然後進行回溯操作。回溯演演算法用於尋找所有的可行解，如果發現一個解不可行，則會捨棄不可行的解。在這道題中，由於每個數位對應的每個字母都可能進入字母組合，因此不存在不可行的解，直接窮舉所有的解即可。

程式碼實現：

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

class Solution {
public:
    void DFS(string& digits, vector<string>& result, string curStr, int curDepth)
    {
        //邊界，找到一種組合，放入陣列中，結束此路徑，向上回溯
        if(curDepth == digits.size())
        {
            if(!curStr.empty())
                result.push_back(curStr);
            return;
        }
        //找到當前字元對映在mapString種的位置
        int curMapIndex = digits[curDepth] - '0';
        string curMap = mapString[curMapIndex];
        //遍歷每一種可能
        for(const auto& ch : curMap)
        {
            DFS(digits, result, curStr+ch, curDepth+1);
        }
    }

    vector<string> letterCombinations(string digits) {
        vector<string> result;
        DFS(digits, result, "", 0);
        return result;
    }
};

組合總數

問題描述：

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

candidates 中的 同一個 數位可以 無限制重複被選取 。如果至少一個數位的被選數量不同，則兩種組合是不同的。

對於給定的輸入，保證和為 target 的不同組合數少於 150 個。

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

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

解題思路：

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

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

2.讓區域性和繼續累加候選的剩餘值

3.區域性和等於目標值，儲存組合，向上回退，尋找其它組合

程式碼實現：

class Solution {
public:
    void DFS(vector<int>& candidates, vector<vector<int>>& result, vector<int> curCand, int prePos, int curSum, int target)
    {
        if(curSum >= target)
        {
            if(curSum == target)
                result.push_back(curCand);
            return;
        }
        for(int i = prePos; i < candidates.size(); i++)
        {
            if(candidates[i] <= target)
            {
                curCand.push_back(candidates[i]);
                DFS(candidates, result, curCand, i, curSum+candidates[i], target);
                //回溯
                curCand.pop_back();
            }
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> curCand;
        DFS(candidates, result, curCand, 0, 0, target);
        return result;
    }
};

活字印書

問題描述：

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

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

範例 1：

輸入：「AAB」

輸出：8

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

解題思路：

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

DFS+回溯：

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

2.繼續給當前組合拼接新的組合，嘗試拼接tiles每一個位置的字元

3.如果當前位置已經在組合中出現過，返回到2，否則標記當前位置，繼續拼接更長的組合

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

當所有位置都已經使用過時，當前遞迴就結束了，繼續向上層DFS回退

最終返回set大小即為組合數目

程式碼實現：

class Solution {
public:
    void DFS(string& tiles, vector<int>& book, string curStr, unordered_set<string>& totolaString)
    {
        if(!curStr.empty())
        {
            totolaString.insert(curStr);
        }
        for(int i = 0; i < tiles.size(); i++)
        {
            //當前字元已用過，跳過
            if(book[i] == 1)
                continue;
            book[i] = 1;
            DFS(tiles, book, curStr+tiles[i], totolaString);
            book[i] = 0;
        }
    }

    int numTilePossibilities(string tiles) {
        vector<int> book(tiles.size(), 0);
        unordered_set<string> totolaString;
        DFS(tiles, book, "", totolaString);

        return totolaString.size();
    }
};

N皇后

問題描述：

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

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

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

解題思路：

DFS+回溯

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

同一列：縱座標相同

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

當前行位置確定後，繼續確定下一行的位置。

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

程式碼實現：

class Solution {
public:
    bool isValidPos(vector<pair<int, int>>& curRet, int row, int col)
    {
        for(pair<int, int> pos : curRet)
        {
            if(pos.second == col || pos.first + pos.second == row + col
               || pos.first - pos.second == row - col)
                return false;
        }

        return true;
    }

    void DFS(vector<vector<pair<int, int>>>& allRet, vector<pair<int, int>>& curRet, int curRow, int n)
    {
        //如果每一行都沒有衝突，則是一種可行的方案
        if(curRow == n)
        {
            allRet.push_back(curRet);
            return;
        }
        //確定當前行的每一個位置是否和已確定的位置有衝突
        for(int i = 0; i < n; i++)
        {
            if(isValidPos(curRet, curRow, i))
            {
                curRet.push_back(make_pair(curRow,i));
                //處理下一行
                DFS(allRet, curRet, curRow+1, n);
                //回溯
                curRet.pop_back();
            }
        }
    }

    vector<vector<string>> transResult(vector<vector<pair<int, int>>>& allRet, int n)
    {
        vector<vector<string>> allMap;
        //所有方案
        for(vector<pair<int, int>> curRet : allRet)
        {
            vector<string> curMap(n, string(n, '.'));
            //一種方案中的所有皇后的位置
            for(pair<int, int> pos : curRet)
            {
                curMap[pos.first][pos.second] = 'Q';
            }
            allMap.push_back(curMap);
        }

        return allMap;
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<vector<pair<int, int>>> allRet;
        vector<pair<int, int>> curRet;
        DFS(allRet, curRet, 0, n);

        return transResult(allRet, n);
    }
};

到此這篇關於C++回溯演演算法深度優先搜尋舉例分析的文章就介紹到這了,更多相關C++ 回溯演演算法內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！


相關文章

  • 德漢姆中學就讀條件 德漢姆中學就讀條件

    <em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011

    2021-06-01 09:32:01

  • 黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列 黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列

    综合看Anker超能充系列的性价比很高，并且与不仅和iPhone12/苹果<em>Mac</em>Book很配，而且适合多设备充电需求的日常使用或差旅场景，不管是安卓还是Switch同样也能用得上它，希望这次分享能给准备购入充电器的小伙伴们有所

    2021-06-01 09:31:42

  • 吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！ 吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！

    除了L4WUDU与吴亦凡已经多次共事，成为了明面上的厂牌成员，吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节，这也是20XXCLUB首次全员合照，王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让

    2021-06-01 09:31:34

  • IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？ IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？

    目前应用IPFS的机构：1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆，历史资料永久保存在 IPFS 6 加

    2021-06-01 09:31:24

  • 有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊 有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊

    开拓者的车机是兼容苹果和<em>安卓</em>，虽然我不怎么用，但确实兼顾了我家人的很多需求：副驾的门板还配有解锁开关，有的时候老婆开车，下车的时候偶尔会忘记解锁，我在副驾驶可以自己开门：第二排设计很好，不仅配置了一个很大的

    2021-06-01 09:30:48

  • iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？ iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？

    不仅是<em>安卓</em>手机，苹果手机的降价力度也是前所未有了，iPhone12也“跳水价”了，发布价是6799元，如今已经跌至5308元，降价幅度超过1400元，最新定价确认了。iPhone12是苹果首款5G手机，同时也是全球首款5nm芯片的智能机，它

    2021-06-01 09:30:45

IT145.com E-mail:sddin#qq.com