题目描述 农民John有很多牛，他想交易其中一头被Don称为The Knight的牛。
这头牛有一个独一无二的超能力，在农场里像Knight一样地跳（就是我们熟悉的象棋中马的走法）。
虽然这头神奇的牛不能跳到树上和石头上，但是它可以在牧场上随意跳，我们把牧场用一个x，y的坐标图来表示。
这头神奇的牛像其它牛一样喜欢吃草，给你一张地图，上面标注了The Knight的开始位置，树、灌木、石头以及其它障碍的位置，除此之外还有一捆草。
现在你的任务是，确定The Knight要想吃到草，至少需要跳多少次。
The Knight的位置用’K’来标记，障碍的位置用’*’来标记，草的位置用’H’来标记。
这里有一个地图的例子：
11 | . . . . . . . . . . 10 | . . . . * . . . . . 9 | . . . . . . . . . . 8 | . . . * . * . . . . 7 | . . . . . . . * . . 6 | . . * . . * . . . H 5 | * . . . . . . . . . 4 | . . . * . . . * . . 3 | . K . . . . . . . . 2 | . . . * . . . . . * 1 | . . * . . . . * . . 0 ---------------------- 1 0 1 2 3 4 5 6 7 8 9 0 The Knight 可以按照下图中的A,B,C,D…这条路径用5次跳到草的地方（有可能其它路线的长度也是5）：
11 | . . . . . . . . . . 10 | . . . . * . . . . . 9 | . . . . . . . . . . 8 | . . . * . * . . . . 7 | . . . . . . . * . . 6 | . . * . . * . . . F< 5 | * . B . . . . . . . 4 | . . . * C . . * E . 3 | .>A . . . . D . . . 2 | . . . * . . . . . * 1 | . . * . . . . * . . 0 ---------------------- 1 0 1 2 3 4 5 6 7 8 9 0 注意： 数据保证一定有解。
样例 输入样例： 10 11 .......... ....*..... .......... ...*.*.... .......*.. ..*..*...H *......... ...*...*.. .K........ ...*.....* ..*....*..
输出样例： 5 一道广搜的”版版”题. 只需用最原始的广搜，改一下方向即可.
时间复杂度 O(n*m),最坏情况全图搜，当然肯定达不到
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
const int N=160;
#define x first
#define y second
typedef pair<int,int> pii;
int n,dis[N][N],m;
char g[N][N],vis[N][N];
pii pre[N][N];
void bfs(int x,int y){
queue<pii>q;
int nx[8]={1,1,-1,-1,2,2,-2,-2},ny[8]={2,-2,2,-2,1,-1,1,-1};
memset(dis,0x3f,sizeof dis);
q.push({x,y});
dis[x][y]=0;
vis[x][y]=1;
while(!q.empty()){
auto now=q.front();
q.pop();
if(g[now.x][now.y]=='H'){
cout<<dis[now.x][now.y]<<endl;
break;
}
//cout<<now.x<<" "<<now.y<<endl;
for(int i=0;i<8;i ){
int a=now.x nx[i],b=now.y ny[i];
if(a<0||b<0||a>m-1||b>n-1)continue;
if(g[a][b]=='*'||vis[a][b])continue;
q.push({a,b});
vis[a][b]=1;
dis[a][b]=min(dis[a][b],dis[now.x][now.y] 1);
if(g[a][b]=='H'){
cout<<dis[a][b]<<endl;
return;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i ){
cin>>g[i];
}
int a,b;
for(int i=0;i<m;i ){
for(int j=0;j<n;j ){
if(g[i][j]=='K'){
bfs(i,j);
return 0;
}
}
}
return 0;
}
