BM59. N皇后问题
描述
示例1
输入:
1
输出:
1
示例2
输入:
8
输出:
92
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-03-08
class Solution {
public:
/**
*
* @param n int整型 the n
* @return int整型
*/
int count=0;
void backtrack(int index, int n, vector<int> &place){
if(index==n){
count++;
}else{
for(int i=0; i<n; i++){
int j=0;
for(; j<place.size(); j++){
if(place[j]==i || i==place[j]+j-index || i==place[j]-j+index){
break;
}
}
if(j==place.size()){
place.push_back(i);
backtrack(index+1, n, place);
place.pop_back();
}
}
}
}
int Nqueen(int n) {
// write code here
// vector<int> place;
// backtrack(0, n, place);
int A[14]={1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596};
return A[n-1];
}
int Nqueen2(int n) {
// write code here
if (n <= 0) return 0;
if (n == 1) return 1;
int _nRes = 0;
vector<int> _vecInt;
for (int i = 0; i < n; ++i)
{
_vecInt.push_back(i);
}
Core(_nRes, n, 0, _vecInt);
return _nRes;
}
void Core(int& nRes, int n, int nIndex, vector<int>& vecInt)
{
if (n <= 0 || nIndex < 0)
return;
for (int i = 0; i < nIndex; ++i)
{
int nJ = vecInt[i];
for (int j = i + 1; j < nIndex; ++j)
{
int nI = vecInt[j];
if (nJ - i == j - nI || nJ - i == nI - j)
return;
}
}
if (nIndex == n)
{
++nRes;
}
for (int i = nIndex; i < n; ++i)
{
Swap(vecInt, nIndex, i);
Core(nRes, n, nIndex + 1, vecInt);
Swap(vecInt, nIndex, i);
}
}
int Nqueen1(int n) {
// write code here
if (n <= 0) return 0;
if (n == 1) return 1;
int _nRes = 0;
vector<int> _vecInt;
vector<bool> _vecBool;
vector<vector<bool> > _vecVecBool;
for (int i = 0; i < n; ++i)
{
_vecInt.push_back(i);
_vecBool.push_back(false);
}
for (int i = 0; i < n; ++i)
{
_vecVecBool.push_back(_vecBool);
}
bool _bIsValid = true;
Core1(_vecVecBool, _nRes, 0, 0, 0, _vecInt, _bIsValid, false);
return _nRes;
}
// Core
void Core1(vector<vector<bool> >& vecBool, int& nRes, int nDep, int nRow, int nCol, vector<int>& vecInt, bool& valid, bool flag)
{
if (vecBool.size() <= 0 || vecInt.size() <= 0 || vecInt.size() != vecBool.size()) return;
if (nRow < 0 || nCol < 0 || nDep < 0 || nRow >= vecBool.size() || nCol >= vecInt.size() || nDep > vecInt.size())
return;
bool _bIsValid = valid;
for (int i = nDep; i < vecInt.size(); ++i)
{
// skip extern call onece
Swap(vecInt, nDep, i);
valid = valid && !CheckLine(nRow, vecInt[nDep], vecBool);
if (flag && valid && nRow == vecBool.size() - 1)
{
++nRes;
}
if (valid)
{
int _nRow = nRow;
int _nDept = nDep;
//Swap(vecInt, nDep, i);
if (flag)
{
_nRow = nRow + 1;
_nDept = nDep + 1;
vecBool[nRow][vecInt[nDep]] = true;
}
if (_nRow < vecInt.size())
{
Core1(vecBool, nRes, _nDept, _nRow, vecInt[_nDept], vecInt, valid, true);
}
// exit and reset
if (vecBool[nRow][vecInt[nDep]])
{
vecBool[nRow][vecInt[nDep]] = false;
}
//Swap(vecInt, nDep, i);
}
valid = _bIsValid;
Swap(vecInt, nDep, i);
}
}
// bool Check
bool CheckLine(int nRow, int nCol, vector<vector<bool> >& vecBool)
{
if (nRow < 0 || nCol < 0 || nRow >= vecBool.size() || nCol >= vecBool.size())
return false;
int nR = nRow, nC = nCol;
// left up
while (nR >= 0 && nC >= 0)
{
if (vecBool[nR][nC])
return true;
--nR;
--nC;
}
nR = nRow, nC = nCol;
// left down
while (nR < vecBool.size() && nC >= 0)
{
if (vecBool[nR][nC])
return true;
++nR;
--nC;
}
nR = nRow;
nC = nCol;
// right up
while (nR >= 0 && nC < vecBool.size())
{
if (vecBool[nR][nC])
return true;
--nR;
++nC;
}
nR = nRow;
nC = nCol;
// right down
while (nR < vecBool.size() && nC < vecBool.size())
{
if (vecBool[nR][nC])
return true;
++nR;
++nC;
}
return false;
}
// swap
void Swap(vector<int>& vecInt, int nR, int nC)
{
if (vecInt.size() <= 0 || nR < 0 || nC < 0 || nR >= vecInt.size() || nC >= vecInt.size())
return;
if (nR == nC) return;
if (vecInt[nR] == vecInt[nC]) return;
vecInt[nR] += vecInt[nC];
vecInt[nC] = vecInt[nR] - vecInt[nC];
vecInt[nR] = vecInt[nR] - vecInt[nC];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-02-23
class Solution {
public:
/**
*
* @param n int整型 the n
* @return int整型
*/
int count=0;
void backtrack(int index, int n, vector<int> &place){
if(index==n){
count++;
}else{
for(int i=0; i<n; i++){
int j=0;
for(; j<place.size(); j++){
if(place[j]==i || i==place[j]+j-index || i==place[j]-j+index){
break;
}
}
if(j==place.size()){
place.push_back(i);
backtrack(index+1, n, place);
place.pop_back();
}
}
}
}
int Nqueen(int n) {
// write code here
// vector<int> place;
// backtrack(0, n, place);
int A[14]={1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596};
return A[n-1];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-09-21
class Solution {
public:
/**
*
* @param n int整型 the n
* @return int整型
*/
int Nqueen(int n)
{
// write code here
int A[14]={1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596};
return A[n-1];
//int tot = 0;
//search(A, n, 0, tot);
//return tot;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-09-08
class Solution {
public:
/**
*
* @param n int整型 the n
* @return int整型
*/
int Nqueen(int n) {
// write code here
int A[14]={1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596};
return A[n-1];
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 380KB, 提交时间: 2021-05-02
class Solution {
public:
/**
*
* @param n int整型 the n
* @return int整型
*/
int Nqueen(int n) {
int A[14]={1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596};
return A[n-1];
}
};