题解 | #跳马游戏#

本题要求到达指定点的最短路径，所以用BFS算法。一般用BFS和DFS算法都是用一个used数组来记录是否访问过，但特殊情况下可以省略，比如本题，把原本的模拟地图的数组ch[N][N]里的元素表示为马到该位置的步数。题目要求如果能到达指定点输出马消耗最少能量（马走的步数），如果不能到达就输出-1。BFS算法和DFS网上有很多模板，就不在此多说了。就说一下我做这题的思路，很简单，把棋盘全初始化为-1，然后用BFS算法遍历出马能到的地方，即马一步能到的地方，两步能到的地方，三步能到的地方...... ，并把该位置由-1置为步数。下面的就很简单了，如果马要到达的位置（x，y）不是-1就代表着能马能走到该位置，并且该位置保存着马到达此位置的步数，直接输出即可。代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=412;
int ch[N][N];//马走的步数
int dx[8]={1,2,2,1,-1,-2,-2,-1};
int dy[8]={2,1,-1,-2,-2,-1,1,2};
struct node{int x,y;};
queue Q;
int n,m,xe,ye;
void bfs(int x,int y){
```
int xx,yy;
```
```
Q.push((node){x,y});
```
```
while(!Q.empty()){
```
```
    node tt=Q.front();
```
```
    Q.pop();
```
```
    for(int i=0;i<8;i++){
```
```
         xx=tt.x+dx[i];
```
```
         yy=tt.y+dy[i];
```

        if(ch[xx][yy]==-1&&xx>=1&&xx<=n&&yy>=1&&yy<=m){

```
            Q.push((node){xx,yy});
```

            ch[xx][yy]=ch[tt.x][tt.y]+1;//★记录步数

```
        }
```
```
    }
```
```
}
```
```
if(ch[xe][ye]!=-1){cout<<ch[xe][ye];}
```
```
else cout<<-1;
```
}
int main(){
```
int a,b;
```
```
cin>>n>>m>>a>>b>>xe>>ye;
```
```
memset(ch,-1,sizeof(ch));
```
```
ch[a][b]=0;
```
```
bfs(a,b);
```
}