n皇后问题
(dfs) $O()$
时间复杂度
剪枝了,不然时间复杂度为2^(N*N)
C++ 代码
// N皇后问题,dfs问题
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int M = 14;
bool dg[M * 2], udg[M * 2], h[M];
int N;
int num = 0;
vector<int> t; // vector赋值很费时间容易TLE
void dfs(int m)
{
if(m == N)
{
num ++;
if(num <= 3)
{
for(auto x : t) cout << x + 1 << " ";
cout << endl;
}
return ;
}
for(int i = 0; i < N; i ++)
{
if(!dg[i + m] && !udg[m + N - i] && !h[i])
{
dg[i + m] = udg[m + N - i] = h[i] = true;
t.push_back(i);
dfs(m+1);
t.pop_back();
dg[i + m] = udg[m + N - i] = h[i] = false;
}
}
}
int main()
{
cin >> N;
dfs(0); // 第0行第0列开始
cout << num;
return 0;
}