BFS与双向BFS---zoj_1505

           http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=505

       题目大意，跳棋，8*8的棋盘，上有4个棋子，给你一个初始状态给你一个结束状态，问能不能在8步之内从初始状态走到结束状态。

       一般的想法，直接暴力DFS，使用状态压缩，状态表偷懒使用set，用时2S

       如果使用双向BFS，从开始节点和结束节点同时开始BFS,需要考虑一个细节问题。就是如果控制两端搜索的步数。即要求一个循环内，两个搜索的步数是相同的。

       其实很简单，设定一个计数n，BFS每一层搜索时，如果有需要push到队列中的装态，就给计数器加1，然后下一层搜索时，pop出n个状态。最后AC，60MS，几乎是0S。

     

#include<cstdio>
#include<queue>
#include<set>
#include<string.h>
#include<algorithm>
using namespace std;
int map[9][9],a[9];
int dirx1[4]={0,0,1,-1};
int diry1[4]={1,-1,0,0};
int dirx2[4]={0,0,2,-2};
int diry2[4]={2,-2,0,0};
struct state
{
	int pos,cnt;	
};
bool check(int r,int c)
{
	if(r<=8&&r>=1&&c<=8&&c>=1)
		return true;
	return false;
}
void getmap(int pos)
{
	memset(map,0,sizeof(map));
	while(pos)
	{
		int c=pos%10;
		pos/=10;
		int r=pos%10;
		pos/=10;
		map[r][c]=1;
	}
}
int getpos()
{
	int r=0;
	for(int i=1;i<=8;++i)
	for(int j=1;j<=8;++j)
	if(map[i][j])
	{
		r=r*10+i;
		r=r*10+j;				
	}
	return r;	
}
bool bfs(int start,int end)
{
	set<int>close;
	close.insert(start);
	queue<state>q;
	state o;
	o.pos=start;
	o.cnt=0;
	q.push(o);
	int x,y;
	while(!q.empty())
	{
		state t=q.front();
		q.pop();
		getmap(t.pos);
		++t.cnt;
		for(int i=1;i<=8;++i)
		{
			for(int j=1;j<=8;++j)
			{
				if(map[i][j])
				{
				for(int d=0;d<4;++d)
				{
					x=i+dirx1[d];	
					y=j+diry1[d];
					if(check(x,y)&&!map[x][y])
					{
						map[i][j]=0;
						map[x][y]=1;
						int pt=getpos();
						if(close.find(pt)==close.end())
						{
							close.insert(pt);
							if(pt==end)
								return true;
							if(t.cnt<8)
							{
								t.pos=pt;
								q.push(t);	
							}
						}
						map[i][j]=1;
						map[x][y]=0;
					}
					x=i+dirx2[d];	
					y=j+diry2[d];
					if(check(x,y)&&!map[x][y]&&map[i+dirx1[d]][j+diry1[d]])
					{
						map[i][j]=0;
						map[x][y]=1;
						int pt=getpos();
						if(close.find(pt)==close.end())
						{
							close.insert(pt);
							if(pt==end)
								return true;
							if(t.cnt<8)
							{
								t.pos=pt;
								q.push(t);	
							}
						}
						map[i][j]=1;
						map[x][y]=0;
					}	
				
				}
				}
			}
		}
	}
	return false;
}
bool dbfs(int start,int end)
{
	set<int>close1;
	set<int>close2;
	close1.insert(start);
	close2.insert(end);
	queue<state>q1;
	queue<state>q2;
	state t1;
	t1.pos=start;
	t1.cnt=0;
	q1.push(t1);	
	t1.pos=end;
	q2.push(t1);
	int x,y;
	int n1=0;
	int m1=1;//计数器
	int n2=0;
	int m2=1;//计数器
	while(!q1.empty()||!q2.empty())
	{
		n1=m1;
		m1=0;
		n2=m2;
		m2=0;
		while(n1--)//保证步数相同
		//if(!q1.empty())
		{
			state t=q1.front();
			q1.pop();
			getmap(t.pos);
			++t.cnt;
			for(int i=1;i<=8;++i)
			{
				for(int j=1;j<=8;++j)
				{
					if(map[i][j])
					{
					for(int d=0;d<4;++d)
					{
						x=i+dirx1[d];	
						y=j+diry1[d];
						if(check(x,y)&&!map[x][y])
						{
							map[i][j]=0;
							map[x][y]=1;
							int pt=getpos();
							if(close2.find(pt)!=close2.end())
								return true;
							if(close1.find(pt)==close1.end())
							{
								close1.insert(pt);
								if(pt==end)
									return true;
								if(t.cnt<4)
								{
									t.pos=pt;
									q1.push(t);
									++m1;
								}
							}
							map[i][j]=1;
							map[x][y]=0;
						}
						x=i+dirx2[d];	
						y=j+diry2[d];
						if(check(x,y)&&!map[x][y]&&map[i+dirx1[d]][j+diry1[d]])
						{
							map[i][j]=0;
							map[x][y]=1;
							int pt=getpos();
							if(close2.find(pt)!=close2.end())
								return true;
							if(close1.find(pt)==close1.end())
							{
								close1.insert(pt);
								if(pt==end)
									return true;
								if(t.cnt<4)
								{
									t.pos=pt;
									q1.push(t);
									++m1;
								}
							}
							map[i][j]=1;
							map[x][y]=0;
						}	
					}
					}
				}
			}
		}
		while(n2--)//保证步数相同
		//if(!q2.empty())
		{
			state t=q2.front();
			q2.pop();
			getmap(t.pos);
			++t.cnt;
			for(int i=1;i<=8;++i)
			{
				for(int j=1;j<=8;++j)
				{
					if(map[i][j])
					{
					for(int d=0;d<4;++d)
					{
						x=i+dirx1[d];	
						y=j+diry1[d];
						if(check(x,y)&&!map[x][y])
						{
							map[i][j]=0;
							map[x][y]=1;
							int pt=getpos();
							if(close1.find(pt)!=close1.end())
								return true;
							if(close2.find(pt)==close2.end())
							{
								close2.insert(pt);
								if(pt==end)
									return true;
								if(t.cnt<4)
								{
									t.pos=pt;
									q2.push(t);
									++m2;
								}
							}
							map[i][j]=1;
							map[x][y]=0;
						}
						x=i+dirx2[d];	
						y=j+diry2[d];
						if(check(x,y)&&!map[x][y]&&map[i+dirx1[d]][j+diry1[d]])
						{
							map[i][j]=0;
							map[x][y]=1;
							int pt=getpos();
							if(close1.find(pt)!=close1.end())
								return true;
							if(close2.find(pt)==close2.end())
							{
								close2.insert(pt);
								if(pt==end)
									return true;
								if(t.cnt<4)
								{
									t.pos=pt;
									q2.push(t);
									++m2;
								}
							}
							map[i][j]=1;
							map[x][y]=0;
						}	
					}
					}
				}
			}
		}			
	}
	return false;
}
int main()
{
	freopen("e:\\zoj\\zoj_1505.txt","r",stdin);
	while(scanf("%d %d %d %d %d %d %d %d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6],&a[7],&a[8])!=EOF)
	{
		memset(map,0,sizeof(map));
		map[a[1]][a[2]]=1;	
		map[a[3]][a[4]]=1;
		map[a[5]][a[6]]=1;
		map[a[7]][a[8]]=1;
		int start=getpos();
		scanf("%d %d %d %d %d %d %d %d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6],&a[7],&a[8]);
		memset(map,0,sizeof(map));
		map[a[1]][a[2]]=1;	
		map[a[3]][a[4]]=1;
		map[a[5]][a[6]]=1;
		map[a[7]][a[8]]=1;
		int end=getpos();
		if(start==end)
		{
			printf("YES\n");
			continue;
		}
		if(dbfs(start,end))
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;	
}