＜冲刺大厂之算法刷题＞回溯算法（四）

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

if (result.size() == ticketNum + 1) {
    return true;
}

for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
    if (target.second > 0 ) { // 记录到达机场是否飞过了
        result.push_back(target.first);
        target.second--;
        if (backtracking(ticketNum, result)) return true;
        result.pop_back();
        target.second++;
    }
}

#include<bits/stdc++.h>
using namespace std;
// unordered_map<出发机场，map<到达机场，航班次数>>
unordered_map<string,map<string,int>> targets;
bool backtracking(int ticketNum,vector<string>& result) {
  if(result.size() == ticketNum+1) { //结束条件
    return true;
  }
  for(pair<const string,int> &target : targets[result[result.size()-1]]) {//以结束点为起始点开往新的航线。 注意：target必须设定为引用，因为要修改targets的属性值 
    if(target.second > 0) { //如果还有航班，就起飞
      result.push_back(target.first) ;
      target.second--;
      if(backtracking(ticketNum,result)) {//如果已经找到了航班次序，则不再进行寻找，直接进行返回
        return true;
      }
      target.second++;
      result.pop_back();
    }
  }
  return false;
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
  targets.clear();
  vector<string> result;
  for(vector<string> vec : tickets) {//vec既可以用引用也可以再复制一份 
    targets[vec[0]][vec[1]]++;//记录映射关系
  }
  result.push_back("JFK") ;
  backtracking(tickets.size(),result);
  return result;
}

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

#include<bits/stdc++.h>
using namespace std;
vector<vector<string>> result;
void backtracing(int row,vector<string>& checkerboard,int n){
  if(row == n){//结束条件 
    result.push_back(checkerboard) ;
    return;
  }
  for(int col = 0;col < n;col++) {
    if(isValid(row,col,checkerboard,n)){
      checkerboard[row][col] = 'Q';
      backtracing(row+1,checkerboard,n);
      checkerboard[row][col] = '.';
    }
  }
}
bool isValid(int row,int col,vector<string>& checkerboard,int n){
  //是否在同一列
  for(int i = 0;i < row;i++) {
    if(checkerboard[i][col] == 'Q'){
      return false;
    }
  }
  //是否在对角线上
  for(int i = row-1,j = col-1; i >=0 && j>=0; i--,j--){
    if(checkerboard[i][j] == 'Q'){
      return false;
    }
  }
  //是否在斜对角线上
  for(int i = row-1,j = col+1; i >=0 && j <n;i--,j++) {
    if(checkerboard[i][j] == 'Q'){
      return false;
    }
  }
  return true;
}
vector<vector<string>> solveNQueens(int n) {
  string s(n,'.');
  vector<string> path(n,s);
  backtracing(0,path,n);
  return result;
}

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

#include<bits/stdc++.h>
using namespace std;
bool backtracing(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]!='.') { //如果已经有数字了，则直接跳过
        continue;
      }
      for(char k = '1'; k <= '9'; k++ ) {
        if(isValid(i,j,k,board)) {
          board[i][j] = k;
          if(backtracing(board)) {//如果找到了方案，则立即返回 
            return true;
          }
          board[i][j] = '.' ;
        }
      }
      return false;
    }
  }
  return true;
}
bool isValid(int row,int col,char k,vector<vector<char>>& board) {
  //同行
  for(int j = 0; j < board[0].size(); j++) {
    if(board[row][j]==k) {
      return false;
    }
  }
  //同列
  for(int i = 0; i < board.size(); i++) {
    if(board[i][col]==k) {
      return false;
    }
  }
  //同一个九宫格
  int startX = ( row / 3) * 3;
  int startY = (col / 3) * 3;
  for(int i = startX ; i < startX+3; i++) {
    for(int j = startY; j<startY+3; j++) {
      if(board[i][j]==k) {
        return false;
      }
    }
  }
  return true;
}
void solveSudoku(vector<vector<char>>& board) {
  backtracing(board);
}