小张用他的一头母牛和吴先生交换了一头“牛骑士”。这头牛有一个独特的能力——在牧场中能像中国象棋中的马一样跑跳（会中国象棋吗？不会？）。当然，这头牛不能跳到岩石或树上，不过能跳到有牧草的地方。这儿有一个宽为X，高为Y的矩形牧场(1 <= X <= 150; 1 <= Y <= 150)。“牛骑士”和其它牛一样喜欢干草。给你一张包含“牛骑士”出发地和树、岩石、灌木或其它障碍物及大包干草等位置信息的地图，确定“牛骑士”得到干草要跳几“跳”。地图中“牛骑士”出发地用’K’表示；障碍物用’*‘表示，牧草用’.'表示，干草所在地用’H’表示。如下图。
“牛骑士”在格子中，有8个方向可以探索。探索顺序按右图中的序号顺序进行。而且“牛骑士”的思维是“一根筋”式的，它会在每一个点按照图中的方向顺序进行探索，也即1号方向能走就走1号方向，不能走才会考虑2号方向，以此类推，直到找到干草为止。
上图中得到干草的步骤在下图中用A,B,C……表示，需要跳4“跳”（如下图）。
第七题 knight
其实就是嘉泽上的牛骑士，可不是骑士牛。
这道题最好用深搜，这题淋漓尽致地展现了深搜的优点，第一次搜到的答案一定是最优解，所以推荐用深搜。
有同学听了还是不理解，就最好跟着代码来进行理解吧。
代码上！
#include <bits/stdc++.h>
using namespace std;
char a[155][155];
int m,n;
void dfs(int dep,int x,int y){
if(x<1||x>n||y<1||y>m||a[x][y]=='*')return;
if(a[x][y]=='H'){
cout<<dep;
exit(0);
}else{
a[x][y]='*';
dfs(dep+1,x+2,y+1);
dfs(dep+1,x+1,y+2);
dfs(dep+1,x-1,y+2);
dfs(dep+1,x-2,y+1);
dfs(dep+1,x-2,y-1);
dfs(dep+1,x-1,y-2);
dfs(dep+1,x+1,y-2);
dfs(dep+1,x+2,y-1);
}
}
int main(){
int x,y;
cin>>m>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='K')x=i,y=j;
}
dfs(0,x,y);
return 0;
}