lintcode33. N皇后问题

Dear 丶 2023-07-05 11:44 3阅读 0赞

n皇后问题是将n个皇后放置在n\*n的棋盘上，皇后彼此之间不能相互攻击(任意两个皇后不能位于同一行，同一列，同一斜线)。  
给定一个整数n，返回所有不同的n皇后问题的解决方案。  
每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。

样例
    例1:
    
    输入:1
    输出:
       [["Q"]]
    
    
    例2:
    
    输入:4
    输出:
    [
      // Solution 1
      [".Q..",
       "...Q",
       "Q...",
       "..Q."
      ],
      // Solution 2
      ["..Q.",
       "Q...",
       "...Q",
       ".Q.."
      ]
    ]
    
    挑战
    你能否不使用递归完成？

思路：

class Solution {
        
    public:
        /*
         * @param n: The number of queens
         * @return: All distinct solutions
         */
        vector<vector<string>> solveNQueens(int n) {
        
            // write your code here
            vector<vector<string>> res;
            vector<int>position(n,-1);
            dfs(res,n,position,0);
            return res;
        }
        void dfs(vector<vector<string>>& res,int n,vector<int>position,int row)
        {
        
            if(row==n)
            {
        
                string str(n,'.');
                vector<string> tmp(n,str);
                for (int i = 0; i < row; i++) {
        
                    tmp[i][position[i]]='Q';
                }
                res.push_back(tmp);
            }
            else
            {
        
                for (int i = 0; i < n; i++) {
        
                    if(judge(i,row,position)) 
                    {
        
                        position[row]=i;
                        dfs(res,n,position,row+1);
                    }
                }
            }
        }
        bool judge(int col,int row,vector<int>position)
        {
        
            for (int i = 0; i < row; i++) {
        
                /* code */
                if(col==position[i]||abs(row-i)==abs(col-position[i]))
                    return false;
            }
            return true;
        }
    };