农民 John 有很多牛,他想交易其中一头被 Don 称为 The Knight 的牛。
这头牛有一个独一无二的超能力,在农场里像 Knight 一样地跳(就是我们熟悉的象棋中马的走法)。
虽然这头神奇的牛不能跳到树上和石头上,但是它可以在牧场上随意跳,我们把牧场用一个 x,y 的坐标图来表示。
这头神奇的牛像其它牛一样喜欢吃草,给你一张地图,上面标注了 The Knight 的开始位置,树、灌木、石头以及其它障碍的位置,除此之外还有一捆草。
现在你的任务是,确定 The Knight 要想吃到草,至少需要跳多少次。
The Knight 的位置用 K 来标记,障碍的位置用 * 来标记,草的位置用 H 来标记。
//#include [HTML_REMOVED]
//#include [HTML_REMOVED]
//#include [HTML_REMOVED]
//#include [HTML_REMOVED]
using namespace std;
typedef pair[HTML_REMOVED] pie;
const int N = 160,inf = 0x3f3f3f3f;
int dx[8] = {-2,-1,1,2,2,1,-1,-2},dy[8] = {-1,-2,-2,-1,1,2,2,1};
char g[N][N];
int dis[N][N];
int n,m,gx,gy;
int bfs(int sx,int sy) {
queue[HTML_REMOVED] q;
q.push({sx,sy});
memset(dis,inf,sizeof dis);
dis[sx][sy] = 0;
g[sx][sy] = ‘*’;
while (q.size()) {
pie p = q.front();
q.pop();
if (p.first == gx && p.second == gy)
break;
for (int i=0; i<8; i) {
int a = p.first + dx[i],b = p.second + dy[i];
if (a>=0 && a[HTML_REMOVED]=0 && b<m && g[a][b]!=’‘ && dis[a][b]==inf) {
q.push({a,b});
g[a][b] = ‘’;
dis[a][b] = dis[p.first][p.second] + 1;
}
}
}
return dis[gx][gy];
}
int main() {
scanf(“%d%d”,&m,&n);
memset(g,’*’,sizeof g);
int sx,sy;
for (int i=0; i<n; i) {
scanf(“%s”,g[i]);
for (int j=0; j<m; j++) {
if (g[i][j] == ‘K’)
sx = i,sy = j;
if (g[i][j] == ‘H’)
gx = i,gy = j;
}
}
printf(“%d\n”,bfs(sx,sy));
return 0;
}