算法
结构体+队列版bfs
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 155,
dx[] = {0, -2, -1, 1, 2, 2, 1, -1, -2},
dy[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
struct Node{
int x, y;
}k, h;
queue <Node> q;
queue <int> Q;
int c, r;
bool b[N][N];
void bfs()
{
q.push(k);
Q.push(1);
while (!q.empty())
{
Node hhh = q.front();
q.pop();
int lalala = Q.front();
Q.pop();
for (int i = 1; i <= 8; i++)
{
int x = hhh.x + dx[i], y = hhh.y + dy[i];
if (x < 1 || y < 1 || x > c || y > r)
continue;
if (b[x][y] == true)
continue;
if (x == h.x && y == h.y)
{
printf("%d\n", lalala);
return;
}
Node tmp = (Node) {x, y};
q.push(tmp);
Q.push(lalala + 1);
b[x][y] = true;
}
}
}
int main()
{
scanf("%d %d", &r, &c);//注意读入顺序
memset(b, 0, sizeof(b));
for (int i = 1; i <= c; i++)
{
char lalala[N];
cin >> lalala + 1;
int len = strlen(lalala + 1);
for (int j = 1; j <= len; j++)
{
if (lalala[j] == 'K')
k = (Node) {i, j}, b[i][j] = true;
if (lalala[j] == 'H')
h = (Node) {i, j};
if (lalala[j] == '*')
b[i][j] = true;
}
}
bfs();
return 0;
}