Day30 回溯第六天

LeetCode 332.重新安排行程

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

LeetCode 51.N皇后

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;
}
};

LeetCode 37.解数独

回溯的最终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);
}
};

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