BFS Algorithm
#include <iostream>
#include <queue>
using namespace std;
using P = pair<int, int>;
static constexpr int dirs[][2] {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2},
{1, 2}, {2, 1}, {2, -1}, {1, -2}};
const int N = 155;
char g[N][N];
int n, m, sx, sy;
int bfs() {
queue<P> q;
q.emplace(sx, sy);
g[sy][sx] = '*'; // mark as seen;
int steps = 0;
while (not q.empty()) {
size_t sz = q.size();
while (sz--) {
const auto [x, y] = q.front(); q.pop();
for (const auto& d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx < 0 || ny < 0 || nx >= n || ny >= m || g[ny][nx] == '*')
continue;
if (g[ny][nx] == 'H') return steps + 1;
q.emplace(nx, ny);
g[ny][nx] = '*'; // mark as seeen;
}
}
++steps;
}
return -1;
}
int main() {
cin >> n >> m;
string line;
for (int y = 0; y < m; ++y) {
cin >> line;
for (int x = 0; x < n; ++x) {
g[y][x] = line[x];
if (g[y][x] == 'K') sx = x, sy = y;
}
}
cout << bfs() << endl;
return 0;
}