【USACO 1.5.4】跳棋的挑战

发布时间:2021-10-19 01:01:42

【问题描述】

检查一个如下的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 (6 <= N <= 14)?表示棋盘是N x N大小的。


【输出格式】

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


【分析】

直接搜索就行了,注意最后两个点打表(大家都会......)。


?



1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7 int num,vis[5][100],order[20];
8 //vis1是横行,2是左下右上
9 int ans,n;
10 void work();
11 void dfs(int lie);
12
13 int main()
14 {
15 //文件操作
16 freopen("checker.in","r",stdin);
17 freopen("checker.out","w",stdout);
18 scanf("%d",&n);
19 if(n==13)
20 {
21 printf("1 3 5 2 9 12 10 13 4 6 8 11 7
");
22 printf("1 3 5 7 9 11 13 2 4 6 8 10 12
");
23 printf("1 3 5 7 12 10 13 6 4 2 8 11 9
");
24 printf("73712
");
25 return 0;
26 }
27 if(n==14){
28 printf("1 3 5 7 12 10 13 4 14 9 2 6 8 11
");
29 printf("1 3 5 7 13 10 12 14 6 4 2 8 11 9
");
30 printf("1 3 5 7 13 10 12 14 8 4 2 9 11 6
");
31 printf("365596
");
32 return 0;
33 }
34 num=n;ans=0;
35 work();
36 printf("%d
",ans);
37 return 0;
38 }
39 void work()
40 {
41 memset(vis,0,sizeof(vis));
42 memset(order,0,sizeof(order));
43 dfs(1);
44 }
45 void dfs(int lie)
46 {
47 if (lie==(num+1))
48 {
49 ++ans;
50 if (ans<=3)
51 {
52 for (int i=1;i<=num;i++)
53 printf("%d ",order[i]);
54 printf("
");
55 }
56 return;
57 }
58 for (int i=1;i<=num;i++)
59 {
60 if (vis[1][i]==0 && vis[2][i+lie]==0 && vis[3][lie-i+num]==0)
61 {
62 order[lie]=i;
63 vis[1][i]=vis[2][i+lie]=vis[3][lie-i+num]=1;
64 dfs(lie+1);
65 vis[1][i]=vis[2][i+lie]=vis[3][lie-i+num]=0;
66 order[lie]=0;
67 }
68 }
69 }

?



转载于:https://www.cnblogs.com/hoskey/p/3788554.html

相关文档

  • 党旗飘飘筑牢红色防火墙战疫示范微党课第十讲观后感心得精选5篇
  • php多态实现,PHP中多态如何实现
  • 单片机中的软硬件防干扰方法
  • 求类似仙界归来的小说
  • 向您推荐一本书
  • Java---Volatile
  • 虚函数与抽象类
  • 金钱之花的演员有哪些
  • 学校党建引领说明报告
  • 感动我的一瞬间作文300字
  • 每年交的280的医保有什么用 每年交的280是医保还是社保
  • 单位拾金不昧表扬信
  • 苹果6splus256g多少钱
  • 读书使我成长作文
  • 复方珍珠解毒口服液说明书
  • 西安机场为什么在咸阳
  • 构造顺序与析构顺序
  • 资生堂百优眼霜好用吗?资生堂百优眼霜怎么样?
  • 七年级语文木兰诗评课稿
  • 关于温馨的生日祝福短信大全
  • 银监会英语面试题目及参考答案***Word版***
  • 《道》最后一章什么意思
  • 梦见很多韭菜是好事吗
  • 华为蓝牙耳机无法被搜索到
  • 内审师不出差时需要做些什么
  • 观察日记500字:雨后的蚯蚓
  • 关于爱情的优美散文随笔
  • 数学教学计划精选多篇
  • 孩子的作业家长如何检查最有效
  • 高温期大闸蟹养殖技术
  • 猜你喜欢

    电脑版