c++【拾遗】 回溯算法
参考链接 https://leetcode-cn.com/problems/n-queens/solution/hui-su-suan-fa-xiang-jie-by-labuladong/
回溯法的核心就是递归调用的过程，在递归调用之前「做选择」，在递归调用之后「撤销选择」
面试题66：矩阵中的路径
设计一个函数，判断在一个矩阵中是否存在一条包含某个字符串所有字符的路径。路径可以从矩阵中任一个元素开始，每一步可以在矩阵中向上下左右移动一格。如果一条路径经过了矩阵中的某一格，那么该路径将不能再进入该格子。
leetcode链接 https://leetcode-cn.com/problems/word-search/submissions/class Solution { public: bool dfs(vector<vector<char>> board, vector<vector<bool>>& visit, int row, int col, int num, string word) { // visit用来标识哪些点被访问过，row为入口节点的行号，col为入口节点的列号，num为入口节点是string word中第几位 if (num == word.length() - 1) { return true; } num++; int round[4][4] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}}; for(int i = 0; i < 4; i++) { if ((row + round[i][0]) < board.size() && (row + round[i][0]) >= 0 && (col + round[i][1]) < board[0].size() && (col + round[i][1]) >= 0 && !visit[row + round[i][0]][col + round[i][1]]) { if (board[row + round[i][0]][col + round[i][1]] != word[num]) { continue; } visit[row + round[i][0]][col + round[i][1]] = true; bool ret; ret = dfs(board, visit, row + round[i][0], col + round[i][1], num, word); if (ret) { return true; } visit[row + round[i][0]][col + round[i][1]] = false; } } return false; } bool exist(vector<vector<char>>& board, string word) { if (word == "") { return true; } if (board.size() == 0) { return false; } // 还需要一个跟board相同大小的visit记录每个节点是否被访问过 vector<vector<bool>> visit; for(int i = 0; i < board.size(); i++) { vector<bool> tmp; for(int j = 0; j < board[0].size(); j++) { tmp.push_back(false); } visit.push_back(tmp); } for(int i = 0; i < board.size(); i++) { for(int j = 0; j < board[0].size(); j++) { if (board[i][j] != word[0]) { continue; } bool ret; visit[i][j] = true; ret = dfs(board, visit, i, j, 0, word); if (ret) { return true; } visit[i][j] = false; } } return false; } };
解题思路：
参考链接 深度优先搜索+剪枝 https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/solution/mian-shi-ti-12-ju-zhen-zhong-de-lu-jing-shen-du-yo/
深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。也就是回溯。
剪枝： 在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问)，则应立即返回，称之为可行性剪枝 。
首先，从矩阵中任选一点作为起点，当矩阵中坐标为(row, col)的格子和路径字符串下标为pathLength的字符一样时，从4个相邻的格子中去定位路径字符串下标为pathLength+1的字符。
如果相邻4个格子都没有匹配到下标为pathLength+1的字符，表明当前路径字符串中下标为pathLength的字符在矩阵中的定位不正确，我们需要回到上一个字符pathLength-1重新定位。
一直重复这个过程，直到路径字符串上多有字符都能在矩阵中找到合适的位置。
面试题67：机器人的运行范围
地上有一个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动，它每次可以上下左右移动一格，但是不能进入行坐标和列坐标数位之和大于k的格子。例如，当k为18时，机器人可以进方格(35,37)，因为3+5+3+7=18。但是不能进入方格(35,38),因为3+5+3+8=19。请问该机器人可以到达多少个格子。
leetcode链接 https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/class Solution { public: int sumBit(int a, int b) { int sum = 0; while(a != 0 || b != 0) { sum = sum + a % 10; sum = sum + b % 10; a = a / 10; b = b / 10; } return sum; } int dfs(int m, int n, int row, int col, int k, vector<vector<bool>>& visit) { if (row < 0 || row >= m || col < 0 || col >= n || sumBit(row, col) > k || visit[row][col]) { return 0; } visit[row][col] = true; return dfs(m, n, row - 1, col, k, visit) + dfs(m, n, row + 1, col, k, visit) + dfs(m, n, row, col - 1, k, visit) + dfs(m, n, row, col + 1, k, visit) + 1; } int movingCount(int m, int n, int k) { int result = 0; vector<vector<bool>> visit; for(int i = 0; i < m; i++) { vector<bool> tmp; for(int j = 0; j < n; j++) { tmp.push_back(false); } visit.push_back(tmp); } result = dfs(m, n, 0, 0, k, visit); return result; } };
解题思路：这个题写的开始完全没明白什么意思。。其实就是各个角度走，走到无法满足条件或者越界就停。可以遍历到的点数=往左走可以遍历到的点数+往右走可以遍历到的点数+往上走可以遍历到的点数+往下走可以遍历到的点数+1（当前起点）。注意已经遍历过的不能再加一遍，因此用visit记录已经遍历的点。
