塔 (t) 姆 (m) 的 (d),沃 (w) 斯 (s) 了 (l)
[USACO2.4] 两只塔姆沃斯牛 The Tamworth Two
题目描述
两只牛逃跑到了森林里。Farmer John 开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为(牛和 John)。
追击在 10×10 的平面网格内进行。一个格子可以是:一个障碍物,两头牛(它们总在一起),或者 Farmer John。两头牛和 Farmer John 可以在同一个格子内(当他们相遇时),但是他们都不能进入有障碍的格子。
一个格子可以是:
.
空地;
*
障碍物;
C
两头牛;
F
Farmer John。
这里有一个地图的例子:
1 2 3 4 5 6 7 8 9 10
| *...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*......
|
牛在地图里以固定的方式游荡。每分钟,它们可以向前移动或是转弯。如果前方无障碍(地图边沿也是障碍),它们会按照原来的方向前进一步。否则它们会用这一分钟顺时针转 90 度。 同时,它们不会离开地图。
Farmer John 深知牛的移动方法,他也这么移动。
每次(每分钟)Farmer John 和两头牛的移动是同时的。如果他们在移动的时候穿过对方,但是没有在同一格相遇,我们不认为他们相遇了。当他们在某分钟末在某格子相遇,那么追捕结束。
读入十行表示地图。每行都只包含 10 个字符,表示的含义和上面所说的相同。保证地图中只有一个 F
和一个 C
。F
和 C
一开始不会处于同一个格子中。
计算 Farmer John 需要多少分钟来抓住他的牛,假设牛和 Farmer John 一开始的行动方向都是正北(即上)。 如果 John 和牛永远不会相遇,输出 0。
输入格式
输入共十行,每行 10 个字符,表示如上文描述的地图。
输出格式
输出一个数字,表示 John 需要多少时间才能抓住牛们。如果 John 无法抓住牛,则输出 0。
样例 #1
样例输入 #1
1 2 3 4 5 6 7 8 9 10
| *...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*......
|
样例输出 #1
提示
翻译来自 NOCOW
USACO 2.4
代码
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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
|
#include<iostream> using namespace std; int forest[11][11]; int cx,cy,fx,fy; bool xysame(){ if(cx==fx&&cy==fy){ return 0; }else return 1; } int main(){ char tmp; for(int i=1;i<=10;i++){ for(int o=1;o<=10;o++){ cin>>tmp; if(tmp=='F'){ fx=o; fy=i; }else if(tmp=='C'){ cx=o; cy=i; }else if(tmp=='*'){ forest[i][o]=1; } } } int dc=0,df=0,movex[4]={0,1,0,-1},movey[4]={-1,0,1,0},ans=0; while(xysame()){ if(forest[cy+movey[dc]][cx+movex[dc]]==0&&cy+movey[dc]>0&&cy+movey[dc]<=10&&cx+movex[dc]>0&&cx+movex[dc]<=10){ cy+=movey[dc]; cx+=movex[dc]; }else{ dc++; if(dc>3) dc=0; } if(forest[fy+movey[df]][fx+movex[df]]==0&&fy+movey[df]>0&&fy+movey[df]<=10&&fx+movex[df]>0&&fx+movex[df]<=10){ fy+=movey[df]; fx+=movex[df]; }else{ df++; if(df>3) df=0; } ans++; if(ans>160000){ cout<<0<<endl; return 0; } } printf("%d",ans); return 0; }
|