bfs模板题;
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define x first
#define y second
const int N=155;
typedef pair<int,int> PII;
char g[N][N];
queue<PII> q;
int C,r;
int d[N][N];
int bfs(int sa,int sb,int ea,int eb)//从起点搜到终点;
{
int i,j;
q.push({sa,sb});
memset(d,-1,sizeof d);//距离初始化为-1;
d[sa][sb]=0;
int dx[8]={-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8]={1, 2, 2, 1, -1, -2, -2, -1};//枚举8个方向;
while(!q.empty())
{
PII t=q.front();
q.pop();
for(i=0;i<8;i++)
{
int tx=t.x+dx[i];
int ty=t.y+dy[i];
if(tx<0||tx>=r||ty<0||ty>=C) continue;
if(g[tx][ty]=='*') continue;
if(d[tx][ty]!=-1) continue;//去掉非答案;
if(g[tx][ty]=='H') //达到目标,目标前一个坐标距离+1;
return d[t.x][t.y]+1;
q.push({tx,ty});
d[tx][ty]=d[t.x][t.y]+1;//每次向周围扩展时距离+1;
}
}
return -1;
}
int main()
{
scanf("%d%d",&C,&r);
int i,j;
PII start;
PII end;
for(i=0;i<r;i++)
for(j=0;j<C;j++)
{
cin>>g[i][j];
if(g[i][j]=='K')
{
start.x=i;
start.y=j;//起点坐标;
}
if(g[i][j]=='H')
{
end.x=i;
end.y=j;//终点坐标;
}
}
printf("%d",bfs(start.x,start.y,end.x,end.y));
return 0;
}