网站优秀网站地址,做宣传册的公司,建网站买服务器,土特产网站平台建设题目描述
一个如下的 6 x 6 的跳棋棋盘#xff0c;有六个棋子被放置在棋盘上#xff0c;使得每行、每列有且只有一个#xff0c;每条对角线#xff08;包括两条主对角线的所有平行线#xff09;上至多有一个棋子。 上面的布局可以用序列 2 4 6 1 3 5 来描述#xff0c;第…题目描述
一个如下的 6 x 6 的跳棋棋盘有六个棋子被放置在棋盘上使得每行、每列有且只有一个每条对角线包括两条主对角线的所有平行线上至多有一个棋子。 上面的布局可以用序列 2 4 6 1 3 5 来描述第 i 个数字表示在第 i 行的相应位置有一个棋子如下
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。 并把它们以上面的序列方法输出解按字典顺序排列。 请输出前 3 个解。最后一行是解的总个数。
输入格式
一行一个正整数 n表示棋盘是 n x 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 n 13。
题目翻译来自NOCOW。
USACO Training Section 1.5 这是深搜的经典题目可以分别对行列对角线做标记来做这道题。其中我们可以发现一条对角线上行和列的和和差的值是一样的。
#include iostream
using namespace std;
const int N 100;
int a[N], b[N], c[N], d[N];//分别表示行列和当前坐标的两条对角线
int n, total;
void queen(int x)
{if (x n){if (total 2)//只输出前三个答案{for (int j 1; j n; j)cout a[j] ;cout \n;}total;return;}else{for (int i 1; i n; i){if (!b[i] (!c[i x]) (!d[x - i n])){a[x] i;b[i] 1;c[i x] 1;d[x - i n] 1;queen(x 1);//遍历下一个b[i] 0;//恢复标记c[i x] 0;d[x - i n] 0;}}}
}
int main()
{cin n;queen(1);//第一个皇后cout total;
}
