检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。
//以下的话来自usaco官方，不代表洛谷观点
特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出(或是找到一个关于它的公式），这是作弊。如果你坚持作弊，那么你登陆USACO Training的帐号删除并且不能参加USACO的任何竞赛。我警告过你了！
一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
输出 #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
此题是标准的DFS题目。有一个非常朴素的想法，就是用一个二维数组vis表示棋子放置后受到影响的格子。每放置一个棋子侯将所有受到影响的格子+1，DFS结束后将这些格子-1。
#include <iostream> #include <stdio.h> #include <math.h> #include <algorithm> #include <string.h> using namespace std; const int MAXN = 1005; int n, s = 0, cnt = 0, cnt2 = 0; int vis[MAXN][MAXN], ans[MAXN][MAXN], map[MAXN][MAXN]; void dfs( int x ) { if ( x > n ) { s++; cnt++; if ( cnt <= 3 ) { cnt2 = 0; for ( int i = 1; i <= n; i++ ) { for ( int j = 1; j <= n; j++ ) { if ( map[i][j] == 1 ) { cnt2++; ans[cnt][cnt2] = j; } } } } return; } for ( int i = 1; i <= n; i++ ) { if ( vis[x][i] == 0 ) { // cout << x << ", " << i << endl; vis[x][i]++; map[x][i] = 1; for ( int j = 1; j <= n; j++ ) { vis[x][j]++; if ( j >= x ) { vis[j][i]++; } if ( x + j <= n && i >= j ) { vis[x + j][i - j]++; } if ( x + j <= n && i + j <= n ) { vis[x + j][i + j]++; } } dfs( x + 1 ); vis[x][i]--; map[x][i] = 0; for ( int j = 1; j <= n; j++ ) { vis[x][j]--; if ( j >= x ) { vis[j][i]--; } if ( x + j <= n && i >= j ) { vis[x + j][i - j]--; } if ( x + j <= n && i + j <= n ) { vis[x + j][i + j]--; } } } } } int main() { cin >> n; dfs( 1 ); for ( int i = 1; i <= 3; i++ ) { for ( int j = 1; j <= n; j++ ) { cout << ans[i][j] << " "; } cout << endl; } cout << cnt << endl; return(0); }
本来以为这个代码会TLE，但是很幸运的是代码AC了。最后一个测试点用了800+ms。
这个代码是可以被优化的，可以用3个一维数组代替二维数组。一个一维数组代表所有列，只要有一个棋子布在某列，则这个数组列对应的元素就置1。类似的2个一维数组代表和2条对角线平行的线。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。