「JoyOI1074」武士风度的牛
题目描述
这头神奇的牛像其它牛一样喜欢吃草，给你一张地图，上面标注了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
输入
第一行： 两个数，表示农场的列数(< =150)和行数(< =150) 第二行..结尾: 如题目描述的图。
输出
一个数，表示跳跃的最小次数。
样例输入
样例输出
提示
Hint：这类问题可以用一个简单的先进先出表（队列）来解决。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include<iostream> using namespace std; struct data{ int x,y,step; }dl[30000]; int m,n; int bi,bj,ei,ej,t=0,w=1; bool mp[151][151]; int xx[8]={1,1,-1,-1,2,-2,2,-2},yy[8]={2,-2,2,-2,1,1,-1,-1}; bool pd(int i,int j) { if(!mp[i][j]&&i>0&&j>0&&i<=m&&j<=n)return 1; return 0; } void bfs() { if(bi==ei&&bj==ej){cout<<dl[t].step;return;} dl[t].x=bi;dl[t].y=bj;dl[t].step=0; while(t<w) { for(int i=0;i<8;i++) { int x=dl[t].x+xx[i]; int y=dl[t].y+yy[i]; if(pd(x,y)) { mp[x][y]=1; dl[w].x=x; dl[w].y=y; dl[w].step=dl[t].step+1; if(dl[w].x==ei&&dl[w].y==ej){cout<<dl[w].step;return;} w++; } } t++; } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { char x; cin>>x; if(x=='*')mp[i][j]=1; if(x=='K'){bi=i;bj=j;} if(x=='H'){ei=i;ej=j;} } bfs(); return 0; } |
OI 课件=>
