BFS
超简单的bfs 一遍ac
#include<bits/stdc++.h>
using namespace std;
int n, m;
const int N = 160;
string a[N];
int vis[160][160];
int sx, sy, ex, ey;
int dx[8] = { -2,-1,1,2,2,1,-1,-2 };
int dy[8] = { -1,-2,-2,-1,1,2,2,1 };
typedef pair<int, int> pii;
struct node {
int x;
int y;
int foot;
node() {
x = 0; y = 0; foot = 0;
}
node(int a, int b, int c) {
x = a; y = b; foot = c;
}
};
int ans;
void bfs(int x, int y) {
queue<node> q;
q.push(node(x, y,0));
vis[x][y] = 1;
while (!q.empty()) {
node t = q.front();
q.pop();
if (t.x == ex && t.y == ey) {
ans = t.foot;
return;
}
for (int i = 0; i < 8; i++) {
int nx = t.x + dx[i];
int ny = t.y+ dy[i];
if (vis[nx][ny])continue;
if (nx >= n || nx < 0 || ny >= m || ny < 0)continue;
if (a[nx][ny] == '*')continue;
q.push(node(nx, ny, t.foot + 1));
vis[nx][ny] = 1;
}
}
}
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == 'K') {
sx = i; sy = j;
}
else if (a[i][j] == 'H') {
ex = i; ey = j;
}
}
}
bfs(sx, sy);
cout << ans << endl;
return 0;
}