LeetCode开心刷题二十七天——51. N-Queens

小灰灰 2023-08-17 15:14 65阅读 0赞

Bonus:

const修饰的i我们称之为符号常量。即，i不能在其他地方被重新赋值了。注意：const int i与int const i是等价的

51. N-Queens

Hard

104047FavoriteShare

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

![8-queens.png][]

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.

Example:

Input: 4
    Output: [
     [".Q..",  // Solution 1
      "...Q",
      "Q...",
      "..Q."],
    
     ["..Q.",  // Solution 2
      "Q...",
      "...Q",
      ".Q.."]
    ]
    Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
    This is a classic problem that has been bothering me for a long time,use back-tracing,finally I 
    can't finish it without looking the answer.SO this problem deverse repeated analysis and trial
    The huahua's answer exchange the position of x and y,but I recovered in my answer!
    a

#include<stdio.h>
    #include<iostream>
    #include<vector>
    #include<algorithm>
    #include<stack>
    #include<string>
    #include<memory>
    #include<memory.h>
    #include<hash_map>
    #include<map>
    #include<list>
    #include<set>
    #include<math.h>
    #include<unordered_map>
    using namespace std;
    
    class Solution {
    public:
        vector<vector<string>> solveNQueens(int n) {
            ans_.clear();
            tmp_=vector<string>(n,string(n,'.'));
            cols_=vector<int>(n,0);
            //row_=vector<int>(n,0);
            diag1_=vector<int>(2*n-1,0);
            diag2_=vector<int>(2*n-1,0);
            nqueens(n,0);
            for(auto i:ans_)
            {
                for(auto j:i)
                {
                    cout<<j<<endl;
                }
                cout<<endl;
                cout<<endl;
            }
            return ans_;
        }
    private:
        vector<vector<string>> ans_;
        vector<string> tmp_;
        vector<int> cols_;
        //don't need row,we loop by row.it don't have chance duplicate
        //vector<int> row_;
        vector<int> diag1_;
        vector<int> diag2_;
        void nqueens(const int n,const int x)
        {
    
            if(x==n)
            {
                ans_.push_back(tmp_);
                return;
            }
            for(int y=0;y<n;y++)
            {
                if(!available(x,y,n)) continue;
                put_(x,y,n,1);
                nqueens(n,x+1);
                put_(x,y,n,0);
            }
        }
    
        bool available(int x,int y,int n)
        {
            return !cols_[y]
            &&!diag1_[x+y]
            &&!diag2_[x-y+n-1];
        }
    
        void put_(int x,int y,int n,bool is_put)
        {
            cols_[y]=is_put;
            diag1_[x+y]=is_put;
            diag2_[x-y+n-1]=is_put;
            tmp_[x][y]=is_put?'Q':'.';
        }
    };
    
    
    int main()
    {
        Solution s;
        int n;
        cin>>n;
        s.solveNQueens(n);
    
    }

Bonus：

[https://zhuanlan.zhihu.com/p/33090662][https_zhuanlan.zhihu.com_p_33090662]

[https://blog.csdn.net/mo\_yihua/article/details/51627809][https_blog.csdn.net_mo_yihua_article_details_51627809]

Two function to handle the input:

input() 除此外还可以接受表达式

# 　　raw\_input() 读取一行，返回字符串 #

special Action：

Because these two functions can only handle string,so use these two methods to change it.

1.Forced type conservation

2.eval() function

a = input("请输入：")
    请输入：123
    >>> type(a)
    <class 'str'>
    
     a = int(input("请输入："))
    请输入：123
    >>> type(a)
    <class 'int'>
    
    相当于整数赋值，eval帮我们去除了引号
     a = eval(input("请输入："))
    请输入：123
    >>> type(a)
    <class 'int'>
    
    input([prompt]) 函数和 raw_input([prompt]) 函数基本类似，但是 input 可以接收一个Python表达式作为输入，并将运算结果返回。
    
    #!/usr/bin/python
    # -*- coding: UTF-8 -*- 
     
    str = input("请输入：");
    print "你输入的内容是: ", str
    这会产生如下的对应着输入的结果：
    
    请输入：[x*5 for x in range(2,10,2)]
    你输入的内容是:  [10, 20, 30, 40]

转载于:https://www.cnblogs.com/Marigolci/p/11274267.html

[8-queens.png]: https://assets.leetcode.com/uploads/2018/10/12/8-queens.png
[https_zhuanlan.zhihu.com_p_33090662]: https://zhuanlan.zhihu.com/p/33090662
[https_blog.csdn.net_mo_yihua_article_details_51627809]: https://blog.csdn.net/mo_yihua/article/details/51627809