说明

John用他的一头母牛和Don先生交换了一头“骑士牛”。这头牛有一个独特的能力——在牧场中能像中国象棋中的马一样跑跳（会中国象棋吗？不会？注意：本题不考虑马被“蹩脚”的情况）。当然，这头牛不能跳到岩石或树上，不过能跳到有牧草的地方。这儿有一个宽为X，高为Y的矩形牧场(1 ≤ X ≤ 150; 1 ≤ Y ≤ 150)。 “骑士牛”和其它牛一样喜欢干草。给你一张包含“骑士牛”出发地和树、岩石、灌木或其它障碍物及大包干草等位置信息的地图，确定“骑士牛”得到干草最少要跳几“跳”。地图中“骑士牛”出发地用'K'表示；障碍物用'*'表示，牧草用'.'表示，干草所在地用'H'表示。这儿有一个示例地图：

骑士牛得到干草的最少步骤在下图中用ABC……表示，最少要跳5“跳”（其它的路径可能超过5“跳”）：

输入格式

第1行: 两个空格隔开的整数: X 和 Y
第2..Y+1行: 第Y-i+2行包含X个没有空格的字符（就像上面的地图一样）：表示第i行的地图。

输出格式

第1行: 一个单独的整数表示最少的得到干草的“跳”数。所有的数据都能得到干草。

样例

输入数据 1

10 11
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
.K........
...*.....*
..*....*..

Copy

输出数据 1

5

bfs模板题

总结反思：

注意：边界问题不要写错。简单的题目一定要注意细节，不能出错。 

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define ll long long
int n,m,vis[157][157];
char a[157][157];
int dx[8]= {-2,-1,-2,-1,1,2,2,1},dy[8]= {-1,-2,1,2,-2,-1,1,2};
struct node {
    int x,y,step;
};
queue<node> q;
bool check(int x,int y) {
    if(x>=0&&y>=0&&x<m&&y<n&&!vis[x][y]&&a[x][y]!='*')
        return true;
    return false;
}
void bfs(int x,int y) {
    while(!q.empty()) {
        node temp=q.front();
        q.pop();
        if(a[temp.x][temp.y]=='H') {
                cout<<temp.step<<endl;
            return ;
        }
        if(vis[temp.x][temp.y])
            continue;
        vis[temp.x][temp.y]=1;
        for(int i=0; i<8; i++) {
            int tx=temp.x+dx[i],ty=temp.y+dy[i];
            if(check(tx,ty)) {
                q.push({tx,ty,temp.step+1});
            }
        }
    }
}
int main() {
    cin>>n>>m;
    for(int i=0; i<m; i++)
        cin>>a[i];
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            if(a[i][j]=='K') {
                q.push({i,j,0});
                bfs(i,j);
                return 0;
            }
        }
    }
    return 0;
}