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");elseprintf("NO\n");}return 0;}?
?