51. N 皇后

定义棋盘

  1. vector<string> chessboard(n,string(n,'.'));
  1. class Solution {
  2. public:
  3.     bool isvalid(int row,int col,int n,vector<string>& chessboard)
  4.     {
  5.         //由于遍历的时候每一行只会有一个Q，所以不用判断行
  6.         //判断列
  7.         for(int i=0;i<row;i++)
  8.         {
  9.             if(chessboard[i][col]=='Q')
  10.                 return false;
  11.         }
  12.         //判断左上角
  13.         for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--)
  14.         {
  15.             if(chessboard[i][j]=='Q')
  16.                 return false;
  17.         }
  18.         //判断右上角
  19.         for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++)
  20.         {
  21.             if(chessboard[i][j]=='Q')
  22.                 return false;
  23.         }
  24.         return true;
  25.     }
  26.     void backtracking(int n,int row,vector<string>& chessboard)
  27.     {
  28.         if(row==n)
  29.         {
  30.             result.push_back(chessboard);
  31.             return;
  32.         }
  33.         for(int col=0;col<n;col++)
  34.         {
  35.             if(isvalid(row,col,n,chessboard))
  36.             {
  37.                 chessboard[row][col]='Q';
  38.                 backtracking(n,row+1,chessboard);
  39.                 chessboard[row][col]='.';
  40.             }
  41.         }
  42.     }
  43.     vector<vector<string>> solveNQueens(int n) {
  44.         vector<string> chessboard(n,string(n,'.'));
  45.         backtracking(n,0,chessboard);
  46.         return result;
  47.     }
  48.     vector<vector<string>> result;
  49. };