题解 P1219 【八皇后】
Uichiha_Itachi
2019-02-06 18:57:34
这题也算是USACO系列题目中少数几道能看得懂是什么意思的经典题了QAQ（详情请见[P2750 贰五语言](https://www.luogu.org/problemnew/show/P2750)）
看到之前的大佬们基本上用的都是记录占领哪条对角线、那条边的算法（处理一维对象），我这里就提供一种其他的方法：以点为单位处理。
以点为单位的核心就是占领、释放点的函数。
占领点：
```cpp
void take(int x,int y)
{
grid[x][y]++;//(x,y) is taken.
for(int i = 1;i <= n;i++)
{
grid[x][i]++;//(x,1...n),(1...n,y) is taken.
grid[i][y]++;
}
for(int i = 1;i <= n;i++)
{
if(valid(x + i,y + i))
{
grid[x + i][y + i]++;
}
if(valid(x - i,y + i))
{
grid[x - i][y + i]++;
}
if(valid(x + i,y - i))
{
grid[x + i][y - i]++;
}
if(valid(x - i,y - i))
{
grid[x - i][y - i]++;
}//Take grid points diagonally.
}
return;
}
```
释放点：
```cpp
void release(int x,int y)
{
grid[x][y]--;//(x,y) is released.
for(int i = 1;i <= n;i++)
{
grid[x][i]--;//(x,1...n),(1...n,y) is Released.
grid[i][y]--;
}
for(int i = 1;i <= n;i++)
{
if(valid(x + i,y + i))
{
grid[x + i][y + i]--;
}
if(valid(x - i,y + i))
{
grid[x - i][y + i]--;
}
if(valid(x + i,y - i))
{
grid[x + i][y - i]--;
}
if(valid(x - i,y - i))
{
grid[x - i][y - i]--;
}//Release grid points diagonally.
}
return;
}
```
copy+pasteの杰作.jpg
如上。其中```grid```二维数组就是题目中说的棋盘的模型。
这里要注意，```grid```中使用```++,--```是有原因的：
如图：](https://cdn.luogu.com.cn/upload/pic/51059.png)
~~配色毒瘤~~
我们发现，若图中的绿色方格即为合法地放了皇后的方格，则图中标红的方格都由不止一个皇后占据。（实际上，这个图上的每一个没有被放皇后的点都是这样的）所以，如果我们只是用```true```,```false```两种符号标记，当回溯取走皇后时，我们就会侵♂犯其他皇后的合法权益。（蛤？）所以，我们这里采用```0```表示空格，非```0```值表示同时占有该格的皇后数。
这样，我们可以保证仅当占有一个格子的最后一个皇后被取走时，该格子才被释放。
后面的就是普通操作了，就不介绍了~~有问题出门左转洛咕网校~~。
代码：（带较详细英文注释）
```
#include <bits/stdc++.h>
using namespace std;
//Definitions.
int n;//Size of the grid
int grid[14][14];//grid map: 0 for 'empty', !=0 for 'filled'.
int sol[14];//the sequence of solutions passed on in recursion.
int solcnt;//number of solutions.
bool valid(int,int);//check validity of gridpoint (x,y).
void take(int,int);//after placeing queen(x,y), undertake grid points.
void print(void);//Print solution if it is one of the first three sols.
void DFS(int);//Depth first search.
int main()
{
cin >> n;
DFS(1);
cout << solcnt;
return 0;
}
bool valid(int x,int y)
{
if((x <= n && y <= n) && (x >= 1 && y >= 1))//In grid.
{
return true;
}
else return false;
}
void take(int x,int y)
{
grid[x][y]++;//(x,y) is taken.
for(int i = 1;i <= n;i++)
{
grid[x][i]++;//(x,1...n),(1...n,y) is taken.
grid[i][y]++;
}
for(int i = 1;i <= n;i++)
{
if(valid(x + i,y + i))
{
grid[x + i][y + i]++;
}
if(valid(x - i,y + i))
{
grid[x - i][y + i]++;
}
if(valid(x + i,y - i))
{
grid[x + i][y - i]++;
}
if(valid(x - i,y - i))
{
grid[x - i][y - i]++;
}//Take grid points diagonally.
}
return;
}
void release(int x,int y)
{
grid[x][y]--;//(x,y) is released.
for(int i = 1;i <= n;i++)
{
grid[x][i]--;//(x,1...n),(1...n,y) is Released.
grid[i][y]--;
}
for(int i = 1;i <= n;i++)
{
if(valid(x + i,y + i))
{
grid[x + i][y + i]--;
}
if(valid(x - i,y + i))
{
grid[x - i][y + i]--;
}
if(valid(x + i,y - i))
{
grid[x + i][y - i]--;
}
if(valid(x - i,y - i))
{
grid[x - i][y - i]--;
}//Release grid points diagonally.
}
return;
}
void print(void)
{
if(solcnt <= 3)//Make sure only print first three solutions.
{
for(int i = 1;i <= n;i++)
{
cout << sol[i] << ' ';
}
cout << endl;
}
return;
}
void DFS(int level)
{
if(level == n + 1)//Reached the end.
{
solcnt++;//Found a solution.
print();//Print solution.
return;//Backtrace.
}
for(int i = 1;i <= n;i++)//Try every (1...13,level).
{
if(valid(i,level) && (!grid[i][level]))//Valid and untaken.
{
sol[level] = i;//Mark as part of solution.
take(i,level);//Take grid points.
DFS(level);//Recurse.
release(i,level);//Release grid points.
sol[level] = 0;//Unmark as part of solution.
}
}
return;
}
```
（带反作弊设计）
题解终。（求过QAQ）