1413: 【作】【基础】骑士巡游
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：7
解决：6
题目描述
马在中国象棋以日字形规则移动，给定n*m大小的棋盘，以及马的初始位置(x，y)和目标位置（s，t），
要求不能重复经过棋盘上的同一个点，计算马至少走多少步可以到达目标位置，所有棋盘保证从初始位置到结束位置一定有路径可达。
输入
测试数据包含一行，为六个整数，分别为棋盘的大小以及初始位置坐标n、m、x、y、s、t。（1≤x，s≤n≤5，1≤y，t≤m≤5）
输出
包含一行，为一个整数，表示马能到达目标位置的最小步数。
样例输入 复制
3 3 1 1 1 3样例输出 复制
2提示
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10
struct coord {
int x,y;
};
queue<coord> Q;
int dep[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dx[9]={0,2,1,-1,1,-2,2,-2,-1};
int dy[9]={0,1,2,2,-2,1,-1,-1,-2};
int n,m,sx,sy,ex,ey;
void bfs(int sx,int sy){
coord tmp = {sx,sy};
Q.push(tmp);
vis[sx][sy]=1;
dep[sx][sy] = 0;
while(!Q.empty()){
coord u=Q.front();
int x=u.x,y=u.y;
Q.pop();
for(int i=0;i<8;i++){
int tx=x+dx[i],ty=y+ dy[i];
if (tx>=1&&tx<=n&&ty>=1&&ty<=m&&vis[tx][ty]!=1){
dep[tx][ty]=dep[x][y]+1;
coord tmp={tx,ty};
Q.push(tmp);
vis[tx][ty]=1;
}
}
}
}
int main(){
memset(dep,-1,sizeof(dep));
cin>>n>>m>>sx>>sy>>ex>>ey;
bfs(sx,sy);
cout<<dep[ex][ey];
return 0;
}