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

折腾了半天,终于不超时了,对位运算也有了更深入的了解,贴上代码,纪念一下poj第21题

Posted by openxxx at 2010-01-24 01:19:50 on Problem 2965
#include<cstdio>
#include<queue>
#include<iostream>
using namespace std;
class cwj
{
public:
	int state;
	int xl;
	int pre;
	int l;
};
bool tt[100000];
int p[20];	
int main()
{
	queue<cwj> q;
	cwj aaa,bbb;
	int i,j,ll,x,k;
	char s[5][10];
	int b=0;
	bool ch;
	p[0]=1;
	for(i=1;i<=16;i++)
		p[i]=2*p[i-1];
	for(i=0;i<4;i++)
	{
		gets(s[i]);
		for(j=0;j<4;j++)
		{
			if(s[i][j]=='+')
			{
				b+=p[i*4+j];
			}
		}
	}
	tt[b]=1;
	for(i=0;i<16;i++)
	{
		aaa.state=b;
		aaa.xl=p[i];
		aaa.pre=i;
		aaa.l=1;
                x=i/4;
                aaa.state^=p[x*4];
                aaa.state^=p[x*4+1];
                aaa.state^=p[x*4+2];
                aaa.state^=p[x*4+3];
                x=i%4;
                aaa.state^=p[x];
                aaa.state^=p[x+4];
                aaa.state^=p[x+8];
                aaa.state^=p[x+12];
                aaa.state^=p[i];
		if(!tt[aaa.state])
		{
		   q.push(aaa);
                     tt[aaa.state]=1;
		}
	}
	while(q.empty()!=true)
	{
		bbb=q.front();
		ll=q.front().l;
		ch=false;
		if(bbb.state==0)
			ch=true;
		if(ch)
		{
			break;
		}
		else
		{
                        aaa.l=bbb.l+1;
                        for(i=bbb.pre+1;i<16;i++)
			{
                                aaa.xl=bbb.xl;
				aaa.xl+=p[i];
				aaa.pre=i;
				aaa.state=bbb.state;
                                x=i/4;
                                aaa.state^=p[x*4];
                                aaa.state^=p[x*4+1];
                                aaa.state^=p[x*4+2];
                                aaa.state^=p[x*4+3];
                                x=i%4;
                                aaa.state^=p[x];
                                aaa.state^=p[x+4];
                                aaa.state^=p[x+8];
                                aaa.state^=p[x+12];
                                aaa.state^=p[i];
		       	        if(!tt[aaa.state])
				{
		                        q.push(aaa);
                                        tt[aaa.state]=1;
				}
			}
			q.pop();
		}
	}
	cout<<ll<<endl;
	for(i=0;i<16;i++)
	{
		k=bbb.xl;
		k&=p[i];
		if(k!=0)
			printf("%d %d\n",i/4+1,i%4+1);
	}	
	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