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

用位运算判断这一列是否可以放

Posted by chinaeli at 2008-10-04 20:19:15 on Problem 1321
不停的wa....给几组测试数据吧~
#include<iostream>
using namespace std;
int mark,n,m,sum,num[10];
char chess[10][10];
void init( )
{
	int i,j;
	memset(num,0,sizeof(num));
	for ( i=0 ; i<n ; i++ )
	{
		scanf("%s",chess[i]);
		for ( j=0 ; j<n ; j++ )
			if ( chess[i][j]=='#' )
				num[i+1]++;
		num[i+1]+=num[i];
	}
	sum=0;
}
void solve ( int line , int cnt )
{
	int i ;
	if ( line==n )
	{
		if ( cnt==m )
			sum++;
		return ;
	}
	if ( cnt+num[n]-num[line]<m || n-line+1+cnt<m )
		return ;
	for ( i=0 ; i<n ; i++ )
	{
		if ( chess[line][i]=='#' && ((mark>>i)&1)==0 )
		{
			solve(line+1,cnt);
			mark|=1<<i;
			solve(line+1,cnt+1);
			mark^=1<<i;
		}
	}
}
int main ( )
{
	int i,j;
	while( scanf("%d%d",&n,&m) && m!=-1 && n!=-1 )
	{
		init();
		for ( i=0 ; i<n ; i++ )
			for ( j=0 ; j<n ; j++ )
				if ( chess[i][j]=='#' )
				{
					mark=1<<j;
					solve(i+1,1);
				}
		printf("%d\n",sum);
	}
}

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