其实可以反着做:
从(1,1)到(x1,y1)、(x2,y2)的距离,即最优解。
还有,queue的STL是很实用的,可以学学,手打队列很难弄的。
参考我的吧:```cpp
#include<bits/stdc++.h>
using namespace std;
const int dx[13]={0,-2,-1,1,2,2,1,-1,-2,2,2,-2,-2};
const int dy[13]={0,1,2,2,1,-1,-2,-2,-1,-2,2,-2,2};
struct node
{
int x,y;
int step;
};
int visit[21][21];
inline bool check(int x,int y)
{
if(x<1||y<1)
return 0;
if(visit[x][y]==1)
return 0;
return 1;
}
inline int bfs(int ex,int ey)
{
memset(visit,0,sizeof(visit));
queue<node>Q;
Q.push(node{1,1,0});
while(!Q.empty())
{
node g=Q.front();
Q.pop();
for(int i=1;i<=12;i++)
{
node t=g;
t.x +=dx[i];
t.y +=dy[i];
t.step +=1;
if(check(t.x,t.y))
{
visit[t.x][t.y]=1;
Q.push(t);
if(t.x ==ex&&t.y==ey)
return t.step ;
}
}
}
}
int main()
{
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
cout<<bfs(x1,y1)<<endl;
cout<<bfs(x2,y2)<<endl;
return 0;
}
```
by Lice @ 2018-07-23 07:56:16