#include <iostream>
using namespace std;
const int N = 8;
char chess[N][N];// 棋盘

int n;
int k;  // 棋子总数
int sum; // 已经下的棋子个数
int C; // 总的方案

bool colFlag[8]; // 标记某列是否可放棋子,TRUE时表示可放

bool Place(char chess[N][N], int i, int j)
{
	//  int row; 
	
	
	// 	int  col;        
	
	// (第1次优化)注释掉第一个for语句后,只判断同一列,不再用判断同一行,从原来的200MS减少为100MS,
	// 	for (col=0; col<=j-1; col++)
	// 	{
	// 		if (chess[i][col] == '+')
	// 		{
	// 			return false;
	// 		}
	// 	}
	// (第2次优化)继续注释掉第二个for语句后,列的判断改用数组来标记,由原来的100MS减少为80MS
	// 	for (row=0; row<=i-1; row++)     
	// 	{                                
	// 		if (chess[row][j] == '+')
	// 		{
	// 			return false;
	// 		}
	// 	}
	return colFlag[j]; 
}

void DFS(char chess[N][N], int i, int j)
{
	
	if (j == n)
	{
		i++;
		j = 0;
	}
	
	if (i == n)
	{
		return ;
	}
	
	if (chess[i][j] == '.')
	{
		DFS(chess,  i, j+1);
	}
	else /*if (chess[i][j] == '#')*/
	{
		DFS(chess,  i, j+1);
		if (Place(chess, i, j))
		{
			sum++;
			colFlag[j] = false;
			if (sum == k)
			{
				C++;
			}
			
			//  DFS(chess, i, j+1); // 没有剪枝,300MS.
	
			DFS(chess, i+1, 0); //(第1次剪枝), 对行进行剪枝,由原来的300MS,变成200MS.
			sum--;
			colFlag[j] = true;
		}
		
		
	}
}


int main()
{
	
	int i,j;
	
	while (cin>>n>>k && n!=-1 && k!=-1)
	{
		sum = 0;
		C = 0;
		for (i=0; i<=8-1; i++)
		{
			colFlag[i] = true;
		}
		for (i=0; i<=n-1; i++)
		{
			for (j=0; j<=n-1; j++)
			{
				cin>>chess[i][j];
			}
		}
		
		DFS(chess, 0, 0);
		cout<<C<<endl;
	}
    return 0;
}

• 好像我写了深搜也没专门剪什么有时0ms有时16ms 。。交流交流。 不懂分析 (535) userfriendly 2009-02-20 20:08:18
  • 我的程序是直接套用了回溯的通用代码,通用性强,但可能灵活性不够导致了效率问题.很郁闷.解数独的时候,也是因为效率不好导致TLE (0) gfedcba 2009-02-20 20:26:41
    • 刚看你的回复，再看看自己的代码，发现自己傻了。。。白白写多一重循环。改了 (331) userfriendly 2009-02-20 21:06:34
      • 你改后，AC的时间是不是每次都变成0MS？？ (0) gfedcba 2009-02-20 23:07:28
        • 没.... AC时间是跟RP挂钩的。 。。 我泪流满面 (0) userfriendly 2009-02-20 23:38:46
    • Re:我的程序是直接套用了回溯的通用代码,通用性强,但可能灵活性不够导致了效率问题.很郁闷.解数独的时候,也是因为效率不好导致TLE (15) blackerJT 2009-10-21 15:48:17
      • Re:我的程序是直接套用了回溯的通用代码,通用性强,但可能灵活性不够导致了效率问题.很郁闷.解数独的时候,也是因为效率不好导致TLE (19) 11111000208 2012-05-03 14:30:55
  • Re:好像我写了深搜也没专门剪什么有时0ms有时16ms 。。交流交流。 不懂分析 (593) 1234556 2010-03-13 20:31:22
    • Re:好像我写了深搜也没专门剪什么有时0ms有时16ms 。。交流交流。 不懂分析 (0) scuwf 2011-11-01 17:58:47
      • Re:好像我写了深搜也没专门剪什么有时0ms有时16ms 。。交流交流。 不懂分析 (38) scuwf 2011-11-01 17:59:34