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

Re:BFS+位运算+回溯路径,G++500MS

Posted by w343051232 at 2012-10-26 13:03:45 on Problem 2965
In Reply To:BFS+位运算+回溯路径,G++500MS Posted by:sanyaocangku at 2012-08-26 13:34:32
> #include<iostream>
> #include<cstdio>
> #include<cstring>
> #include<queue>
> using namespace std;
> #define N 5
> int sd,key=0;
> int vis[1<<16];
> int dir[16] = {4383,8751,17487,34959,4593,8946,17652,35064,7953,12066,
> 20292,36744,61713,61986,62532,63624};
> struct node
> {
> 	int sum,num,step;
> }cur;
> struct path
> {
> 	int x,pre;
> }p[100001];
> void f(int index)
> {
> 	if(index)
> 	{
> 		f(p[index].pre);
> 		printf("%d %d\n",p[index].x/4+1,p[index].x%4+1);
> 	}
> }
> void bfs()
> {
> 	int i,j,k;
> 	cur.sum=sd;
> 	cur.num=0;
> 	cur.step=0;
> 	p[1].pre=0;
> 	queue<node>q;
> 	q.push(cur);
> 	while(!q.empty())
> 	{
> 		node b=q.front();
> 		q.pop();
> 		if(b.sum==0)
> 		{
> 			printf("%d\n",b.step);
> 			f(b.num);
> 			return;
> 		}
> 		for(i=0;i<16;i++)
> 		{
> 			node a=b;
> 			a.sum^=dir[i];
> 			if(!vis[a.sum])
> 			{
> 				a.num=++key;
> 				a.step++;
> 				p[key].pre=b.num;
> 				p[key].x=i;
> 				q.push(a);
> 				vis[a.sum]=1;
> 			}
> 		}
> 	}
> }
> int main()
> {
> 	int i,j;
> 	char s[5];
> 	for(i=0;i<4;i++)
> 	{
> 		scanf("%s",s);
> 		for(j=0;j<4;j++)
> 		{
> 			if(s[j]=='+')
> 			{
> 				sd+=(1<<i*4+j);
> 			}			
> 		}
> 	}
> 	bfs();
> 	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