算法思路
从起点和终点分别开始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;
}
}
网友评论