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 suda1227401034 at 2013-04-27 20:03:27 on Problem 1753
#include<iostream>
#include<algorithm>
using namespace std;
#define max 65536

struct node
{
	bool map[4][4];
	int step;
}q[max*2];
int visit[max],tar1=0,tar2=max-1;
int pow2[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};


/*void init()
{
	int m=1;
	for(int i=0;i<16;i++)
	{
		pow2[i]=m;
		m*=2;
	}
}*/
int trans(bool a[4][4])
{
	int m=0;
	for(int i=0;i<16;i++)
	{
		m=m+a[i/4][i%4]*pow2[i];
	}
	return m;
}

int bfs(node s)
{
	int h=0,t=1;
	q[h]=s;
	q[h].step=0;
	visit[trans(s.map)]=1;

	node cur,next;
	while(h<t)
	{
		cur=q[h];
		
		if(trans(cur.map)==tar1||trans(cur.map)==tar2)
		{
			return cur.step;
		}

		for(int i=0;i<4;i++)
		{
			for(int j=0;j<4;j++)
			{
				next=cur;
				if(i>0)
				{
					next.map[i-1][j]=!cur.map[i-1][j];
				}
				if(i<3)
				{
					next.map[i+1][j]=!cur.map[i+1][j];
				}
				if(j>0)
				{
					next.map[i][j-1]=!cur.map[i][j-1];
				}
				if(j<3)
				{
					next.map[i][j+1]=!cur.map[i][j+1];
				}
				next.map[i][j]=!cur.map[i][j];
				
				if(!visit[trans(next.map)])
				{
					next.step=cur.step+1;
					q[t++]=next;
					visit[trans(next.map)]=1;
				}
			}
		}
		h++;
	}
	return -1;
}
int main()
{
//	init();
	node cur;
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			char c;
			cin>>c;
			c=='w'?cur.map[i][j]=1:cur.map[i][j]=0;
		}
	}
	memset(visit,0,sizeof(visit));
	int k;
	k=bfs(cur);
	if(k==-1)
	{
		cout<<"Impossible"<<endl;
	}
	else
	{
		cout<<k<<endl;
	}
}

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