Shulou(Shulou.com)06/01 Report--

Editor to share with you the C++ backtracking algorithm depth-first search example analysis, I hope you will learn something after reading this article, let's discuss it together!

All the playing cards are arranged

If there are three playing cards numbered 1x 3 and three boxes numbered 1m 3, now you need to put three cards into three boxes, and each box can only put one card, how many different ways are there?

The idea of solving the problem: suppose you try according to the face value of the card from small to large, that is, No. 1 plate is put into the first box. Continue to go back in this order, and by the time you finish the third box, the cards in your hand have been used up, and then you will reach the end of the box. At this time, a method of release has been completed, that is, the road has come to an end and needs to turn back and return to the previous box. Here, go back to the third box, recycle the cards in the third box, and then try to see if you can put other cards. But there is only one card No. 3 in hand at this time, so you need to go back to Box 2. Following the above steps will produce all the results in turn. Use an array of book to mark whether you have this card in your hand.

Dfs (processing logic for the current step)

{

1. Judge whether the boundary is already dark: go up and back.

two。 Try every possibility of the moment

3. After identifying a possibility, move on to the next step Dfs (next step)

}

Code implementation:

Void DFS (vector& boxs, vector& books, int n, int index) {if (index > = n + 1) {for (int I = 1; I = col) continue / / if the color meets the requirements and has not been rendered before, continue rendering if (image [curx] [curY] = = oldColor & & book [curX] [curY] = = 0) {DFS (image, book, curX, curY, newColor, oldColor, row, col) }} vector floodFill (vector& image, int sr, int sc, int newColor) {int row = image.size (); int col = image [0] .size (); int oldColor = image [sr] [sc]; vector book (row, vector (col, 0)); DFS (image, book, sr, sc, newColor, oldColor, row, col); return image;}} The surrounding area.

Problem description:

Give you a m x n matrix board, with several characters'X 'and' O', find all the areas surrounded by'X 'and fill all the' O'in these areas with'X'.

Problem-solving idea: starting from the O of each edge, as long as it is connected with the O of the edge, it is not surrounded.

1. First of all, look for every O on the side, if not, it means that all the Os are surrounded.

two。 For each O on the edge for dfs diffusion, first mark each O on the edge with a special symbol (except X and O). Replace the O adjacent to it with a special symbol, and each new location does the same dfs operation.

3. After all the diffusion is over, the position of the special symbol (connected to the boundary) is restored to O, and the original position of O (not connected to the boundary) is replaced by X.

Code implementation:

Int nextP [4] [2] = {{- 1,0}, {1,0}, {0,-1}, {0,1}}; class Solution {public: void DFS (vector& board, int curX, int curY, int row, int col) {board [curX] [curY] = 'Agar; 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.empty [x] [y]! ='A'& & board [x] [y]! ='X') DFS (board, x, y, row, col);}} void solve (vector& board) {if (board.empty ()) return; int row = board.size () Int col = board [0] .size (); / / the first and last lines 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& grid, vector& 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& grid) {if (grid.empty () return 0; int row = grid.size () Int col = grid [0] .size (); int num = 0; vector book (row, vector (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& 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 letterCombinations(string digits) { vector 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& candidates, vector& result, vector 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 (); iTunes +) {if (candidates [I]

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.