AcWing-N皇后

row【x】是查看第x行是否占用
col【y】是查看第y列是否占用
dg【i】是表示第i条主对角线是否被占用
udg【i】是表示第i条副对角线是否被占用
下图中相同颜色对应的对角线表示同一条主对角线，副对角线也同理！这里有15条对角线，n=8，一共有2*n-1条对角线！

N皇后
怎么理解dg[x + y]和udg[x - y + n]，dg是主对角线，↘，udg是副对角线，↗
因为45°的斜线y=x+b是不能存在皇后的，135°的y=-x+b也是。
方程:
$\{\begin{array}{ll}-b=x-y& x\ge 0,y\ge 0----(1)\\ b=x+y& x\ge 0,y\ge 0----(2)\end{array}$
其中dg【i】是表示第i条主对角线是否被占用，udg【i】是表示第i条副对角线是否被占用.式子（1）表明我们的-b可以访问到负数，因为数组是不能访问负数下标的，所以需要对udg访问到的下标进行处理，
最极端情况下，udg需要访问到下标最小值是X_min-Y_max
X_min=0
Y_max=n-1
$(X_{min}-Y_{max}{)}_{min}=n-1,因此我们直接给这个加上n-1就好了$，标准答案是加上n，实际上我尝试了只加上n-1也是ok的，可以通过OJ测试，需要同步在代码注释的三处地方同步修改！
实际上，只要你加上的数大于n-1就行了，并且在代码注释3处同步修改即可！

#include <iostream>using namespace std;const int N = 10;int n;
bool row[N], col[N], dg[N * 2], udg[N * 2];
char g[N][N];void dfs(int x, int y, int s)
{if (s > n) return;if (y == n) y = 0, x ++ ;if (x == n){if (s == n){for (int i = 0; i < n; i ++ ) puts(g[i]);puts("");}return;}g[x][y] = '.';dfs(x, y + 1, s);//在第x行尝试放置第s个皇后在(x,y+1)的位置if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) //udg[x - y + n]这里只加上n-1也是ok的{row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;//标记占用，udg[x - y + n]这里只加上n-1也是ok的g[x][y] = 'Q';//放置皇后dfs(x, y + 1, s + 1);//在第x行尝试放置第s+1个皇后在(x,y+1)的位置g[x][y] = '.';//不放置皇后了，撤回！row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;//解除占用标记，udg[x - y + n]这里只加上n-1也是ok的}
}int main()
{cin >> n;dfs(0, 0, 0);return 0;
}