第七题 knight
kradcigam
2019-06-29 11:49:56
## 第七题 knight
其实就是嘉泽上的牛骑士，可不是骑士牛。
这道题最好用**深搜**，这题淋漓尽致地展现了深搜的优点，第一次搜到的答案一定是最优解，所以推荐用深搜。
有同学听了还是不理解，就最好跟着代码来进行理解吧。
代码上！
```cpp
#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;
}
```