学步园

一直听到大家在说双向BFS，自己从来没用，于是今天也找了个题目写着玩。

直接写的，没有参照别人代码。

候选结点，用了两个队列保存。至于已经到达的状态，一个数组足矣。从起点出发到达的用正数表示，从终点出发到达的用负数表示。

然后当整数碰到负数，说明找到了，结束。

#include <iostream><br /> #include <algorithm><br /> using namespace std;<br /> int n;<br /> int move[8][2]={2,1,2,-1,-2,1,-2,-1,1,2,1,-2,-1,2,-1,-2};<br /> bool check(int x,int y)<br /> {<br /> if(x<0||x>=n||y<0||y>=n) return false;<br /> else return true;<br /> }<br /> struct node<br /> {<br /> int x,y;<br /> int step;<br /> }queue[160000],queue2[160000];<br /> int visit[160000];<br /> int first,first2,end,end2;<br /> int store(node& a,int from)<br /> {<br /> int pos=a.x*n+a.y;<br /> if(visit[pos]*from<0)<br /> {<br /> printf("%d/n",abs(visit[pos])+abs(a.step)-2);<br /> return 2;//另一端已经到达该点<br /> }<br /> else if(visit[pos]==0)<br /> {<br /> visit[pos]=a.step*from;<br /> return 0;//该点未曾访问<br /> }<br /> return 1;//自己曾经到达，没什么意思<br /> }<br /> bool advance(node a[],int& first,int& end,int from)<br /> {<br /> int ans;<br /> for(int i=0;i<8;i++)<br /> {<br /> a[end].step=a[first].step+1;<br /> a[end].x=a[first].x+move[i][0];<br /> a[end].y=a[first].y+move[i][1];<br /> if(!check(a[end].x,a[end].y)) continue;<br /> ans=store(a[end],from);<br /> if(ans==2) return true;<br /> else if(ans==0) end++;<br /> }<br /> first++;<br /> return false;<br /> }<br /> int main()<br /> {<br /> int T,ans;<br /> scanf("%d",&T);<br /> for(int t=0;t<T;t++)<br /> {<br /> memset(visit,0,sizeof(visit));<br /> scanf("%d",&n);<br /> first=first2=0;<br /> end=end2=1;<br /> scanf("%d%d",&queue[0].x,&queue[0].y);<br /> scanf("%d%d",&queue2[0].x,&queue2[0].y);<br /> queue[0].step=queue2[0].step=1;<br /> if(store(queue[0],1)==2) continue;<br /> if(store(queue2[0],-1)==2) continue;<br /> while(1)<br /> {<br /> if(advance(queue,first,end,1)) break;<br /> if(advance(queue2,first2,end2,-1)) break;<br /> }<br /> }<br /> return 0;<br /> }<br />