即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

checker Challenge 跳棋的挑战

编程语言 longlong_long 25℃ 0评论
本文目录
[隐藏]

题目如下:


checker Challenge 跳棋的挑战


检查一个如下的6 x 6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行,每列,每条对角线(包括两条主对角线的所有对角线)上都至多有一个棋子。

1.1 2 3 4 5 6

2.1 | | O | | | | |

3.2 | | | | O | | |

4.3 | | | | | | O |

5.4 | O | | | | | |

6.5 | | | O | | | |

7.6 | | | | | O | |

上面的布局可以用序列2 4 6 1 3 5 来描述,第i个数字表示在第i行的相应位置有一个棋子,如下:


行号 1 2 3 4 5 6


列号 2 4 6 1 3 5


这只是跳棋放置的一个解.请编写一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。


解按字典顺序排列。请输出前3个解。最后一行是解的总个数。


INPUT FORMAT


一个数字N (6 <= N <= 13) 表示棋盘是N x N 大小的。


SAMPLE INPUT(checker.in)


6


OUTPUT FORMAT


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


SAMPLE OUTPUT(checker.out)


2 4 6 1 3 5


3 6 2 5 1 4


4 1 5 2 6 3


4


解题思路:


这一题实际上就是一个N皇后问题,用DFS就可以过,每对角线可以表示为:


b[行+列]和b1[列-行+N-1] ,列为:b2[列]


所以代码如下:

#include
#include
#include
using namespace std;
int n,ans=0;
int bj1[50],b[100],a[50],bj[100];
void dfs(int k) {
    if(k==n+1) {
        if(ans<3) {//输出前三个 
            for(int i=1; icout<" ";//输出 
            cout<//总是+1 
        return ;//返回 
    }
    for(int i=1; i<=n; i++) {
        if(bj1[i]==0&&b[i+k]==0&&bj[i-k+n-1]==0) {//保证使得每行,每列,每条对角线(包括两条主对角线的所有对角线)上都至多有一个棋子 
            bj1[i]=1;
            b[i+k]=1;
            bj[i-k+n-1]=1;
            a[k]=i;
            dfs(k+1);
            bj1[i]=0;
            b[i+k]=0;
            bj[i-k+n-1]=0;
        }
    }
}
int main() {
    cin>>n;//输入 
    dfs(1);//从第一行开始搜索 
    cout<//输出总和 
    return 0;
}

转载请注明:CodingBlog » checker Challenge 跳棋的挑战

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情