dfs刷题矩阵搜索问题
文章目录
N皇后
题解
1. 画出决策树
2. 全局变量：ret用来统计结果，path统计每次的路径，checkcol检查行有没有Q，checkdig1检查主对角线有没有Q，checkdig2检查副对角线有没有Q
3. 剪枝：使用哈希表的策略，每一行不需要检查，每次都递归每一行该放的不会出现攻击，主对角线斜率一样，利用y-x = b，每一条线上截距是相同的，如果出现相同的就表明放过了Q，y-x可能为负数所以加上了n，副对角线y + x = b，和主对角线类似
4. 回溯：将列，主对角线和副对角线变为false，path[row][col]恢复为点
5. 递归出口：行越界的时候填完矩阵
代码
classSolution{ public:// 检查列,主对角线和副对角线// 行每次都只放一个不用检查,不会出现攻击bool checkcol[10],checkdig1[20],checkdig2[20]; vector<vector<string>> ret; vector<string> path;int n; vector<vector<string>>solveNQueens(int _n){ n = _n; path.resize(n);for(int i =0;i < n;i++){ path[i].append(n,'.');}dfs(0);return ret;}voiddfs(int row){ if(n == row){ ret.push_back(path);return;}for(int col =0;col < n;col++)// 放置每一行{ if(!checkcol[col]&&!checkdig1[row + col]&&!checkdig2[col-row+n]){ path[row][col]='Q'; checkcol[col]= checkdig1[row + col]= checkdig2[col-row+n]=true;dfs(row+1);// 恢复现场 checkcol[col]= checkdig1[row + col]= checkdig2[col-row+n]=false; path[row][col]='.';}}}};有效的数独
题解
1. 算法原理：去遍历这个数独，如果遇到了数字就判断这个数字是否在这一行，这一列，这一个方格中，如果不在就标记为true，如果在就直接返回false，说明出现了第二次了
2. bool checkrow[i][nums]：用来检查这一行是否存在nums这个数
bool checkcol[j][nums]：用来检查这一列是否存在nums这个数
bool check[i/3][j/3][nums]：用来检查小方格中是否存在nums这个数，除3是把9 * 9的矩阵分为0，1，2下标的3*3的小方格，刚好第一个小方格中0，1，2下标的数除3都是0，第二，三个小方格也是如此
代码
classSolution{ public:bool checkrow[9][10];// 检查行bool checkcol[9][10];// 检查列bool check[3][3][10];// 检查小方格boolisValidSudoku(vector<vector<char>>& board){ for(int row =0;row <9;row++){ for(int col =0;col <9;col++){ if(board[row][col]!='.'){ int nums = board[row][col]-'0';if(checkrow[row][nums]|| checkcol[col][nums]|| check[</
