【代码随想录算法训练Day30】LeetCode 332.重新安排行程、LeetCode 51.N皇后、LeetCode 37.解数独

看了半天也没看懂题，以后再来。

N皇后题目是回溯算法的经典题目，这道题的难度在思维。我们如何才能正确遍历二维数组，如何确定皇后的摆放位置，这些是本题的难点。
在拆分题意后本体其实清晰了很多，我们要做的首先是确定这个格子能不能放皇后，也就是isValid()函数的实现，判断所在行列以及斜线是否有元素，然后就是标准的回溯模板，递归实现放皇后的操作。
本体只要循环到最后一行就是满足条件的，直接加入结果集即可。

class Solution {
public:vector<vector<string>> res;void backtrack(int n,int row,vector<string>& chessboard){if(row==n){res.push_back(chessboard);return;}for(int col=0;col<n;col++){if(isValid(row,col,chessboard,n)){chessboard[row][col]='Q';backtrack(n,row+1,chessboard);chessboard[row][col]='.';}}}bool isValid(int row,int col,vector<string>& chessboard,int n){for(int i=0;i<row;i++)if(chessboard[i][col]=='Q') return false;for(int i=row-1,j=col-1;i>=0 && j>=0;i--,j--)if(chessboard[i][j]=='Q') return false;for(int i=row-1,j=col+1;i>=0 && j<n;i--,j++)if(chessboard[i][j]=='Q') return false;return true;}vector<vector<string>> solveNQueens(int n) {vector<string> chessboard(n,string(n,'.'));backtrack(n,0,chessboard);return res;}
};

回溯的最终boss：二维回溯。我们用回溯只能定位行和列，这里还要继续处理每一个格子里填1~9是否合理。我们要边递归边判断，如果空格里有填法，返回true，如果没有填法，就撤回来。

class Solution {
public:bool backtrack(vector<vector<char>>& board){for(int i=0;i<board.size();i++){for(int j=0;j<board[0].size();j++){if(board[i][j]=='.'){for(char k='1';k<='9';k++){if(isValid(i,j,k,board)){board[i][j]=k;if(backtrack(board)) return true;board[i][j]='.';}}return false;}}}return true;}bool isValid(int row,int col,char val,vector<vector<char>>& board){for(int i=0;i<9;i++)if(board[row][i]==val) return false;for(int j=0;j<9;j++)if(board[j][col]==val) return false;int startRow=(row/3)*3;int startCol=(col/3)*3;for(int i=startRow;i<startRow+3;i++)for(int j=startCol;j<startCol+3;j++)if(board[i][j]==val)return false;return true;}void solveSudoku(vector<vector<char>>& board) {backtrack(board);}
};

今天的题好难，感觉得多做几次，以后多来思考几次。