剑指offer学习笔记：8.6 回溯法

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记录已经遍历的点。