Uchiha_Itachi 的博客

Uchiha_Itachi 的博客

题解 P1219 【八皇后】

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

这题也算是USACO系列题目中少数几道能看得懂是什么意思的经典题了QAQ(详情请见P2750 贰五语言

看到之前的大佬们基本上用的都是记录占领哪条对角线、那条边的算法(处理一维对象),我这里就提供一种其他的方法:以点为单位处理。

以点为单位的核心就是占领、释放点的函数。

占领点:

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

如上。其中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)