塔 (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;
}
|