神刀安全网

怎样应对IT面试与笔试-(八)

Backtracking(回溯法)

51. N-Queens

经典的N皇后问题,将n个皇后放到n*n的棋盘上,使得两两皇后不能攻击(同一行、同一列、同一斜线上的皇后都会自动攻击)
我们需要返回所有的可行方法,Q表示皇后位置,.表示空位。
像题目中给出的例子:

Input: 4 Output: [  [".Q..",  // Solution 1   "...Q",   "Q...",   "..Q."],   ["..Q.",  // Solution 2   "Q...",   "...Q",   ".Q.."] ] 

先给出代码:

class Solution { public:     vector<vector<string>> solveNQueens(int n) {         vector<vector<string> > res;         vector<string> nQueens(n,string(n,'.'));         solveNQueens(res,nQueens,0,n);         return res;     }     void solveNQueens(vector<vector<string> >&res, vector<string>& nQueens,int row,int &n)     {         if(row == n)         {             res.push_back(nQueens);             return;         }         for(int col = 0; col != n; ++col)         {             //isValid是用来保证每一行、每一列和对角线都没有冲突的皇后             if(isValid(nQueens,row,col,n))             {                 nQueens[row][col] = 'Q';                 //递归,深度优先搜索                 solveNQueens(res,nQueens,row + 1, n);                 //清理现场                 nQueens[row][col] = '.';             }         }     }     bool isValid(vector<string> &nQueens,int row,int col,int &n)     {         for(int i = 0; i != row; ++i)         {             if(nQueens[i][col] == 'Q')                 return false;         }         for(int i = row -1,j = col -1; i >=0 && j >=0;--i,--j)         {             if(nQueens[i][j] == 'Q')                 return false;         }         for(int i = row -1,j = col + 1; i >= 0 && j <n; --i,++j)         {             if(nQueens[i][j] == 'Q')                 return false;         }         return true;     } }; 

以2*2的简单棋盘说明:

怎样应对IT面试与笔试-(八)

51.png

(1)箭头上的数字表示了程序的执行流程
(2)红色箭头是进行深度优先探索过程
(3)黑色箭头是进行回溯(清理现场)过程

回溯作为一种算法思想,通常都是使用递归这种方式来实现

怎样应对IT面试与笔试-(一)
怎样应对IT面试与笔试-(二)
怎样应对IT面试与笔试-(三)
怎样应对IT面试与笔试-(四)
怎样应对IT面试与笔试-(五)
怎样应对IT面试与笔试-(五-1)
怎样应对IT面试与笔试-(六)
怎样应对IT面试与笔试-(七)
怎样应对IT面试与笔试-(八)
怎样应对IT面试与笔试-(九)
怎样应对IT面试与笔试-(十)
怎样应对IT面试与笔试-(十一)
怎样应对IT面试与笔试-(十二)
怎样应对IT面试与笔试-(十三)
怎样应对IT面试与笔试-(十四)
怎样应对IT面试与笔试-(十五)
怎样应对IT面试与笔试-(十六)

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 怎样应对IT面试与笔试-(八)

分享到:更多 ()