acwing188. 武士风度的牛

题目

农民 John 有很多牛，他想交易其中一头被 Don 称为 The Knight 的牛。

这头牛有一个独一无二的超能力，在农场里像 Knight 一样地跳（就是我们熟悉的象棋中马的走法）。

虽然这头神奇的牛不能跳到树上和石头上，但是它可以在牧场上随意跳，我们把牧场用一个 x，y 的坐标图来表示。

这头神奇的牛像其它牛一样喜欢吃草，给你一张地图，上面标注了 The Knight 的开始位置，树、灌木、石头以及其它障碍的位置，除此之外还有一捆草。

现在你的任务是，确定 The Knight 要想吃到草，至少需要跳多少次。

The Knight 的位置用 K 来标记，障碍的位置用 * 来标记，草的位置用 H 来标记。

题解

#include<iostream>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;

typedef pair<int, int> PII;

const int N=155;
char g[N][N];
int dist[N][N];
int n,m,ans;
PII q[N*N];

int  bfs(PII start){
    memset(dist,-1, sizeof dist);
    dist[start.x][start.y]=0;
    int dx[8]={1,2,-1,-2,1,2,-1,-2},dy[8]={2,1,2,1,-2,-1,-2,-1};

    int hh=0,tt=0;
    q[0]=start;
    while(hh<=tt){
        PII t=q[hh++];
        for(int i=0;i<8;i++){
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a<0||a>=n||b<0||b>=m)continue;
            if(g[a][b]=='*')continue;
            if(dist[a][b]!=-1)continue;
            if(g[a][b]=='H')
                return dist[t.x][t.y]+1;
            dist[a][b]=dist[t.x][t.y]+1;    
            q[++tt]={a,b};
        }
    }
    return -1;
    
}

int main(){
    cin>>m>>n;
    PII start;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            cin>>g[i][j];
            if(g[i][j]=='K')start={i,j};
        }
           
    
    cout<<bfs(start)<<endl;
            
    return 0;
}