Acwing 188. 武士风度的牛

题目分析：

  • 马走日，求最短路

注意：

g[a][b] == '*' (bushi g[a][b] != '.',这样走不到H

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;

#define x first
#define y second
#define el endl
#define pii pair<int,int>
#define mm(a,x) memset(a,x,sizeof a)
#define mk make_pair

const int N = 155;

int n,m;
char g[N][N];
int dist[N][N];
int xa,ya,xb,yb;
int dx[8] = {-2,-1,1,2,2,1,-1,-2};
int dy[8] = {1,2,2,1,-1,-2,-2,-1};

void bfs(int sx,int sy){
    queue<pii> q;
    q.push({sx,sy});
    mm(dist,-1);
    dist[sx][sy] = 0;
    while(q.size()){
        pii t = q.front();
        q.pop();

        if(t.x == xb && t.y == yb) return ;

        for(int i = 0; i < 8; i ++ ){
            int a = t.x + dx[i],b = t.y + dy[i];
            if(a < 0 || a > n - 1 || b < 0 || b > m - 1) continue;
            if(g[a][b] == '*' || dist[a][b] != -1) continue;
            dist[a][b] = dist[t.x][t.y] + 1;
            q.push({a,b});
        }
    }
}
int main(){
    cin >> m >> n;
    for(int i = 0; i < n; i ++ ) cin >> g[i];
    for(int i = 0; i < n; i ++ ){
        for(int j = 0; j < m; j ++ ){
            if(g[i][j] == 'K') xa = i,ya = j;
            if(g[i][j] == 'H') xb = i,yb = j;
        }
    }
    bfs(xa,ya);
    cout<<dist[xb][yb];        
    return 0;
}