Knight Moves POJ - 1915（双向广度优先搜索）

算法思路

从起点和终点分别开始bfs

while(!q1.empty()||!q2.empty()){
   if(!q1.empty()){
       node e=q1.front();
       q1.pop()
       while(对其的一个临界点){
          if(在q2中出现过）搜索完毕，return 两个bfs的步数之和
          else if(没有在q1中出现过）入队}
}
if(!q2.empty(){
  操作与前面相同……
}
}

题目

https://vjudge.net/problem/POJ-1915

代码

#include<cstdio>
#include<iostream>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=310;
int vis[maxn][maxn];
int step[maxn][maxn];
int n;
struct node{
int x,y;
};
queue<node>q1;
queue<node>q2;
int dx[]={2,2,-2,-2,1,1,-1,-1};
int dy[]={1,-1,1,-1,-2,2,2,-2};
bool check(node a){
  if(a.x>=0&&a.x<n&&a.y>=0&&a.y<n)
    return true;
  return false;
}
int bfs(node s,node t){
    while(!q1.empty())
        q1.pop();
    while(!q2.empty())
        q2.pop();
   vis[s.x][s.y]=1;//起点开始的搜索队列标记1
   q1.push(s);
   vis[t.x][t.y]=2;//终点开始的搜索队列标记2
   q2.push(t);
   step[s.x][s.y]=0;
   step[t.x][t.y]=0;
   while(!q1.empty()||!q2.empty()){
      if(!q1.empty()){
         node e=q1.front();
         q1.pop();
         int st=step[e.x][e.y];
         for(int i=0;i<8;i++){
                node t;
         t.x=e.x+dx[i];t.y=e.y+dy[i];
            if(check(t)){
                if(vis[t.x][t.y]==2){
                    return step[t.x][t.y]+st+1;
                }
                else if(!vis[t.x][t.y]){
                    vis[t.x][t.y]=1;
                    step[t.x][t.y]=st+1;
                    q1.push(t);
                }
            }
         }
      }
      if(!q2.empty()){
         node e=q2.front();
         q2.pop();
         int st=step[e.x][e.y];
         for(int i=0;i<8;i++){
                node t;
         t.x=e.x+dx[i];t.y=e.y+dy[i];
            if(check(t)){
                if(vis[t.x][t.y]==1){
                    return step[t.x][t.y]+st+1;
                }
                else if(!vis[t.x][t.y]){
                    vis[t.x][t.y]=2;
                    step[t.x][t.y]=st+1;
                    q2.push(t);
                }
            }
         }
      }

   }
}
int main(){
   int tt;
   cin>>tt;
   while(cin>>n){
    memset(vis,0,sizeof(vis));
    //memset(step,0,sizeof(step));
    node s;node t;
    cin>>s.x>>s.y>>t.x>>t.y;
    if(s.x==t.x&&s.y==t.y) cout<<0<<endl;
    else cout<<bfs(s,t)<<endl;
   }
}