LeetCode 51. N-Queens

题目

N 皇后问题。

其实就是DFS或者BFS的入门题。

要是可以用位运算来模拟皇后的摆放和棋盘，那么代码就很优雅了。

代码语言：javascript复制

class Solution {
public:
    vector<vector<string>> ans;
    int a[100][100];
    int m;
    vector<vector<string>> solveNQueens(int n) {
        
        m=n;
        memset(a,0,sizeof(a));
        fun(0);
        
        return ans;
    }
      
    
    void fun(int pos)
    {
        if(pos==m)
        {
            ans.push_back(getString());
            return;
        }
        for(int i=0;i<m;i  )
        {
            if(a[pos][i]==0)
            {
                a[pos][i]=1;
                setLock(pos,i,2);
                fun(pos 1);
                setLock(pos,i,-2);
                a[pos][i]=0;
            }
        }
    }
    void setLock(int x,int y,int num)
    {
        for(int i=x 1;i<m;i  )
        {
            a[i][y] =num;
        }
        int tag=1;
        for(int i=x 1;i<m;i  )
        {
            if(y tag<m)
                a[i][y tag] =num;
            if(y-tag>=0)
                a[i][y-tag] =num;
            
            tag  ;
        }
    }
    
    vector<string> getString()
    {
        vector<string> res;
       
        for(int i=0;i<m;i  )
        {
            string s="";
            for(int j=0;j<m;j  )
            {
                if(a[i][j]==1)
                {
                    s ='Q';
                }
                else
                    s ='.';
            }
            res.push_back(s);
        }
        return res;
    }
    
};

dfs

0 人点赞