............................
题目描述
农民 John 有很多牛,他想交易其中一头被 Don 称为 The Knight 的牛。
这头牛有一个独一无二的超能力,在农场里像 Knight 一样地跳(就是我们熟悉的象棋中马的走法)。
虽然这头神奇的牛不能跳到树上和石头上,但是它可以在牧场上随意跳,我们把牧场用一个 x,y 的坐标图来表示。
这头神奇的牛像其它牛一样喜欢吃草,给你一张地图,上面标注了 The Knight 的开始位置,树、灌木、石头以及其它障碍的位置,除此之外还有一捆草。
现在你的任务是,确定 The Knight 要想吃到草,至少需要跳多少次。
The Knight 的位置用 K 来标记,障碍的位置用 * 来标记,草的位置用 H 来标记。
这里有一个地图的例子:
11 | . . . . . . . . . .
10 | . . . . * . . . . .
9 | . . . . . . . . . .
8 | . . . * . * . . . .
7 | . . . . . . . * . .
6 | . . * . . * . . . H
5 | * . . . . . . . . .
4 | . . . * . . . * . .
3 | . K . . . . . . . .
2 | . . . * . . . . . *
1 | . . * . . . . * . .
0 ----------------------
1
0 1 2 3 4 5 6 7 8 9 0
The Knight 可以按照下图中的 A,B,C,D… 这条路径用 5 次跳到草的地方(有可能其它路线的长度也是 5):
11 | . . . . . . . . . .
10 | . . . . * . . . . .
9 | . . . . . . . . . .
8 | . . . * . * . . . .
7 | . . . . . . . * . .
6 | . . * . . * . . . F<
5 | * . B . . . . . . .
4 | . . . * C . . * E .
3 | .>A . . . . D . . .
2 | . . . * . . . . . *
1 | . . * . . . . * . .
0 ----------------------
1
0 1 2 3 4 5 6 7 8 9 0
注意: 数据保证一定有解。
输入格式
第 1 行: 两个数,表示农场的列数 C 和行数 R。
第 2..R+1 行: 每行一个由 C 个字符组成的字符串,共同描绘出牧场地图。
输出格式
一个整数,表示跳跃的最小次数。
数据范围
1≤R,C≤150
样例
blablabla
C++ 代码
#include <iostream>
#include <queue> // 要先明确需要用什么,是pair 还是结构体
using namespace std;
typedef pair<int,int> PII;
const int N = 155;
PII path[N][N];
struct node
{
int x,y,s;
node(int x,int y,int s):x(x),y(y),s(s){};
}; // ### s(x); 混蛋,调试了一个小时
char map[N][N];
bool g[N][N];
int n,m,xx,yy;
int a[]={-2,-2,-1,1,2,2,1,-1};
int b[]={-1,1,2,2,1,-1,-2,-2};
void bfs(int x,int y,int u)
{
queue<node>q;
q.push(node(x,y,u));
g[x][y]=true;
while(!q.empty())
{
auto p=q.front();
q.pop();
if(p.x==xx&&p.y==yy)
{
printf("%d\n",p.s);
}
for(int i=0;i<8;i++) // 可不能条件反射般的写4啊!!!
{
int xa=p.x+a[i];
int yb=p.y+b[i];
int d=p.x;
int y=p.y;
if(xa>=0&&xa<n&&yb>=0&&yb<m&&!g[xa][yb]&&map[xa][yb]!='*')
{
q.push(node(xa,yb,p.s+1));
g[xa][yb]=true;
}
}
}
}
int main()
{
int x,y;
cin>>m>>n; // 一定要看清楚! 一定要看清楚!! 一定要看清楚!!!
for(int i=0;i<n;i++)
for(int k=0;k<m;k++)
{
cin>>map[i][k];
if(map[i][k]=='K')
{
x=i;
y=k;
}
if(map[i][k]=='H')
{
xx=i;
yy=k;
}
}
bfs(x,y,0);
return 0;
}