[USACO1.5]八皇后 Checker Challenge

题目描述

一个如下的 $6\times 6$ 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列 $246135$ 来描述，第 $i$ 个数字表示在第 $i$ 行的相应位置有一个棋子，如下：

行号 $123456$

列号 $246135$

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 $3$ 个解。最后一行是解的总个数。

输入格式

一行一个正整数 $n$，表示棋盘是 $n\times n$ 大小的。

输出格式

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

样例 #1

样例输入 #1

6

样例输出 #1

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

提示

【数据范围】
对于 $100\%$ 的数据，$6\le n\le 13$。

题目翻译来自NOCOW。

USACO Training Section 1.5

思路分析

这个题其实就是在八皇后的基础上，稍微做了一点变动，下面根据代码分析本题

题意分析

这里先大概分析一下题意，题目意思就是问我们，在一个n * n的棋盘上，把n个皇后放在不同行不同列不同斜线的放法有多少？怎么放，记录怎么放的。

代码分析

dfs深度优先搜索模板（做本题前建议背熟且理解这个模板）

如果这个模板不懂的，建议配合dfs入门题组合数一起理解，后面我会出dfs的分析

#include <iostream>
using namespace std;
void dfs(int u)
{
	if(....)  // 这里填结束条件
	{
			//这里面可以操作我们的答案
			return；
	}
	
	for(int i = 0; i< n; i++) // 这里是枚举每一个子分支
	{
		if（）// 子分支满足一定条件
		{
			dfs(u+1); // 在对子分支进行dfs
		}
	}
}

int main()
{
	cin>>n;
	dfs(0);
	return 0;
}

ac demo

#include <iostream>
#include <cstring>
using namespace std;

const int N = 20;
int n, ans;
int g[N][N];
bool col[N], a[N], b[N];//a数组和b数组分别标记对角线

void dfs(int u)
{
    if(u == n)
    {
        if(ans < 3)//根据题目意思，我们只输出前三次的答案
        {
            
        for(int i = 0; i < n; i++)
            {   
            for(int j = 0; j < n; j++)
            if(g[i][j] == 1) cout<<j+1<<" ";
            }
        cout<<endl;
        }
        ans ++;//记录答案的个数
        
        return ;
    }
    
    for(int i = 0; i < n; i++)
    {
        if(!col[i] && !a[u+i] && !b[n - u + i])
        {
            col[i] = a[u+i] = b[n-u+i] = true;
            g[u][i] = 1;
            dfs(u + 1);
            col[i] = a[u+i] = b[n-u+i] = false;
            g[u][i] = 0;
        }
    }
}
int main()
{
    cin>>n;
    
    dfs(0);
    cout<<ans<<endl;
    return 0;
}