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

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

Bonus:

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

N-Queens

Hard

104047FavoriteShare

The n-queens puzzle is the problem of placing n queens on an n×nchessboard 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.

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://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]