这是手册上的深搜题,首先我们要将棋盘的位置标记,因为行和列都不同,所以必须用两个数组分别来存
点的横坐标和纵坐标,然后开始一个棋子一个棋子地摆上去,计算有几种摆法。
#include#include using namespace std; const int N = 8*8 + 10; int x[N], y[N]; bool visx[N], visy[N]; int n, k, m; long long cnt; char ch[N]; void dfs( int a, int ans) { if( k == ans) cnt ++; for( int i = a; i < m; i ++) if( !visx[ x[i] ] && !visy[ y[i] ]) { visx[ x[i] ] = true; visy[ y[i] ] = true; dfs( i + 1, ans + 1); visx[ x[i] ] = false; visy[ y[i] ] = false; } } int main() { while( true) { cin >> n >> k; if( n == -1 && k == -1) break; m = 0; for( int i = 0; i < n; i ++) { cin >> ch; for( int j = 0; j < n; j ++) { if( ch[j] == '#') { x[m] = i; y[m] = j; m ++; } } } memset( visx, false, sizeof visx); memset( visy, false, sizeof visy); cnt = 0; dfs( 0, 0); cout << cnt << endl; } return 0; }
下面这个代码超时,没搞懂原因
#include#include using namespace std; const int N = 8*8 + 10; int x[N], y[N]; bool vis[N][N]; int n, k, m; long long cnt; char ch[N]; void dfs( int a, int ans) { if( k == ans) cnt ++; for( int i = a; i < m; i ++) if( !vis[ x[i] ][ y[i] ]) { vis[ x[i] ][ y[i] ] = true; dfs( i + 1, ans + 1); vis[ x[i] ][ y[i] ] = false; } } int main() { while( true) { cin >> n >> k; if( n == -1 && k == -1) break; m = 0; for( int i = 0; i < n; i ++) { cin >> ch; for( int j = 0; j < n; j ++) { if( ch[j] == '#') { x[m] = i; y[m] = j; m ++; } } } memset( vis, false, sizeof (vis) ); cnt = 0; dfs( 0, 0); cout << cnt << endl; } return 0; }