Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

先后进行1次强剪枝和2次优化之后,从原来的300MS变成80MS,请教牛人们0MS的实现方法.可否帮我将下面的代码由80MS改成0MS.感激不尽

Posted by gfedcba at 2009-02-20 17:51:11 on Problem 1321 and last updated at 2009-02-20 17:55:19
#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;
}



Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator