bfs求最短路问题。

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 155;

int n,m;
char g[N][N];
int vis[N][N];

int bfs(PII start,PII end)
{
    queue<PII>q;//坐标
    memset(vis,-1,sizeof(vis));
    vis[start.x][start.y] = 0;
    q.push(start);

    int dx[] = {-2,-1,1,2,2,1,-1,-2};
    int dy[] = {1,2,2,1,-1,-2,-2,-1};

    while(!q.empty())
    {
        PII t = q.front();
        q.pop();

        for(int i = 0;i<8;i++)
        {
            int x = t.x+dx[i],y = t.y+dy[i];
            if(x<0||x>=n||y<0||y>=m) continue;
            if(g[x][y]=='*') continue;
            if(vis[x][y]!=-1) continue;
            vis[x][y]=vis[t.x][t.y]+1;// 记录新坐标的访问步数
            if(make_pair(x,y)==end) return vis[x][y];
            q.push({x,y});
        }
    }
}
int main()
{
    cin>>m>>n;
    PII start,end;//起始坐标和终点坐标
    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};
            else if(g[i][j]=='H') end = {i,j};
        }
    }
    cout<<bfs(start,end)<<endl;
    return 0;
}