P1219 [USACO1.5] 八皇后 Checker Challenge

题目描述

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

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

行号

列号

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

6

输出 #1

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

说明/提示

【数据范围】
对于 的数据，。

题目翻译来自NOCOW。

USACO Training Section 1.5

题解思路

这是一道比较经典BFS问题，重点在于“每一列、每一斜线至多只有一个数字”的限定条件判定。

1、列的唯一性判定：我们可以给定一个和列同长的bool数组，通过判定数组上对应位的真假来判定唯一性。

2、斜线的唯一性判定：我们发现任一条“左上-右下”斜线都满足row+col为一常数，而任一“右上-左下”斜线都满足row-col为一常数，则也可以通过bool数组映射判断的方式解决。（注意：row-col可能为负数，我们需要通过加上一常数将其转回正数。）

具体cpp代码如下：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<unordered_map>
using namespace std;

int readint(){ 
	char ch=getchar();
	int x=0;
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9'){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x;
}
const int Max_n=15;
int col_of_row[Max_n]={};
bool check[3][Max_n+Max_n]={};
int n=0,sum=0;

void f(int row){
    if(row>n){
        sum++;
        if(sum>3) return ;
        else{
            for(int i=1;i<=n;i++) printf("%d ",col_of_row[i]);
            printf("\n");
            return ;
        }
    }
    
    for(int col=1;col<=n;col++){
        if(!check[0][col] && !check[1][row+col] && !check[2][row-col+n]){
            col_of_row[row]=col;
            check[0][col]=check[1][row+col]=check[2][row-col+n]=true;
            f(row+1);
            check[0][col]=check[1][row+col]=check[2][row-col+n]=false; //回溯
        }
    }
}
int main(){
	n=readint();
    f(1);
    printf("%d",sum);
	return 0;
}