# Uchiha_Itachi 的博客

### 题解 P1219 【八皇后】

posted on 2019-02-06 18:57:34 | under 题解 |

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;
}

copy+pasteの杰作.jpg

#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;
}

（带反作弊设计）