【leetcode】 N-Queens

地址

https://leetcode.com/problems/n-queens/description/

题目

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]

思路

傻逼暴力题,居然还是hard

代码

class Solution {
public:
    int n,ul[100],ux[100],uy[100];
    char mp[100][100];
    vector<vector<string>> ans;
    vector<string>tmp;
    
    void dfs(int x)
    {
        if(x==n)
        {
            tmp.clear();
            for(int i=0;i<n;i++)
            {
                string tb;
                for(int j=0;j<n;j++)
                    tb+=mp[i][j];
                cout<<tb<<endl;
                tmp.push_back(tb);
            }
            ans.push_back(tmp);
            cout<<endl;
            return ;
        }
        for(int j=0;j<n;j++)
        if(ul[j]==0&&ux[j-x+50]==0&&uy[n-x-j+50]==0)
        {
            ul[j]=ux[j-x+50]=uy[n-x-j+50]=1;
            mp[x][j]='Q';
            dfs(x+1);
            mp[x][j]='.';
            ul[j]=ux[j-x+50]=uy[n-x-j+50]=0;
        }
    }
    vector<vector<string>> solveNQueens(int N) {
        n=N;
        memset(ul,0,sizeof ul);
        memset(ux,0,sizeof ux);
        memset(uy,0,sizeof uy);
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            mp[i][j]='.';
        dfs(0);
        return ans;
    }
};