n皇后问题
Description
有一个n*n的棋盘，你要在这个棋盘上放上n个皇后，使得她们不能相互攻击。当然为了使得问题更加有趣，我们在棋盘上限定了一些位置使得这些位置上不能放皇后。
Format
Input
第一行两个数n和m ，表示在一个n*n的棋盘上放n个皇后，有m个受限位置。
接下来m行每行两个数，x和y，表示第x行，第y列这个位置不可以放皇后。
Output
一行一个数 ans，表示总的方案数。
Samples
输入数据 1
4 1
1 2
[Copy](javascript:
输出数据 1
1
[Copy](javascript:
Limitation
对于20%的数据m=0,n<=6
对于60%的数据 m<=n*n n<=10
对于100%的数据 m<=n*n n<=17
#include <bits/stdc++.h>
using namespace std;
#define up(l, r, i) for (int i = l, END##i = r; i <= END##i; ++i)
#define dn(r, l, i) for (int i = r, END##i = l; i >= END##i; --i)
// #define int long long
#define ll long long
#define fast \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
const int N = 114514 / 1000;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int t[N][N], a[N], m;
bool isSafe(int x, int y, int n)
{
if (t[x][y] == 1) return false;
up(0, x - 1, i)
{
if (a[i] == y)
{
return false;
}
}
for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; --i, --j)
{
if (a[i] == j)
{
return false;
}
}
for (int i = x - 1, j = y + 1; i >= 0 && j < n; --i, ++j)
{
if (a[i] == j)
{
return false;
}
}
return true;
}
void dfs(int x, int n, int &cnt)
{
if (x == n && t[x][n] == 0)
{
++cnt;
return;
}
up(0, n - 1, y)
{
if (isSafe(x, y, n))
{
a[x] = y;
dfs(x + 1, n, cnt);
a[x] = 0;
}
}
}
int f(int n)
{
vector<int> a(n, 0);
int cnt = 0;
dfs(0, n, cnt);
return cnt;
}
int main()
{
fast;
int n;
cin >> n;
cin >> m;
if (m == n * n)
{
cout << 0;
return 0;
}
if (m == n * n - 1)
{
cout << 1;
return 0;
}
up(1, m, i)
{
int t1, t2;
cin >> t1 >> t2;
t[t1 - 1][t2 - 1] = 1;
}
cout << f(n) << endl;
return 0;
}