当前位置 博文首页 > AiY..的博客：洛古P1518—两只塔姆沃斯牛
题目描述
两只牛逃跑到了森林里。Farmer John 开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为（牛和 John）。
追击在 10×1010 \times 1010×10 的平面网格内进行。一个格子可以是：一个障碍物，两头牛（它们总在一起），或者 Farmer John。两头牛和 Farmer John 可以在同一个格子内（当他们相遇时），但是他们都不能进入有障碍的格子。
一个格子可以是：
. 空地；
* 障碍物；
C 两头牛；
F Farmer John。
这里有一个地图的例子：
*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......
牛在地图里以固定的方式游荡。每分钟，它们可以向前移动或是转弯。如果前方无障碍（地图边沿也是障碍），它们会按照原来的方向前进一步。否则它们会用这一分钟顺时针转 90 度。 同时，它们不会离开地图。
Farmer John 深知牛的移动方法，他也这么移动。
每次（每分钟）Farmer John 和两头牛的移动是同时的。如果他们在移动的时候穿过对方，但是没有在同一格相遇，我们不认为他们相遇了。当他们在某分钟末在某格子相遇，那么追捕结束。
读入十行表示地图。每行都只包含 10 个字符，表示的含义和上面所说的相同。保证地图中只有一个 F 和一个 C。F 和 C 一开始不会处于同一个格子中。
计算 Farmer John 需要多少分钟来抓住他的牛，假设牛和 Farmer John 一开始的行动方向都是正北（即上）。 如果 John 和牛永远不会相遇，输出 0。
输入格式
输入共十行，每行 10 个字符，表示如上文描述的地图。
输出格式
输出一个数字，表示 John 需要多少时间才能抓住牛们。如果 John 无法抓住牛，则输出 0。
输入输出样例
输入 #1
*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......
输出 #1
49
解题思路：
模拟，把每次牛和农夫走的点都进行对比，如果相等就输出时间，我假如时间大于50000就是代表不会相遇
程序代码：
#include<stdio.h>
char s[20][20];
int next[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int tx1,ty1,tx2,ty2;
int main()
{
int i,j,k1,k2,n,m,p1,q1,p2,q2,flag,sum,v1,v2,w1,w2;
sum=0;
for(i=0;i<10;i++)
scanf(" %s",s[i]);
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{
if(s[i][j]=='F')
{
tx1=p1=i;ty1=q1=j;
}
if(s[i][j]=='C')
{
tx2=p2=i;ty2=q2=j;
}
}
flag=0;
v1=v2=-1;
w1=w2=0;//最初农夫和牛向北方向走
k1=k2=0; //记录旋转的方向
while(1)
{
sum++;
tx1=tx1+v1;
ty1=ty1+w1;
if(ty1<0||ty1>9||tx1<0||tx1>9||s[tx1][ty1]=='*')//防止数组会越界
{
k1++;
tx1=p1;ty1=q1; //如果走到墙或者走出的区域则让坐标还是等于上一步坐标，该步为旋转方向
v1=next[k1%4][0];w1=next[k1%4][1];
}
else
{
p1=tx1;q1=ty1;//把农夫的坐标保存一下
}
tx2=tx2+v2;
ty2=ty2+w2;
if(tx2<0||tx2>9||ty2<0||ty2>9||s[tx2][ty2]=='*')
{
k2++;
tx2=p2;ty2=q2;
v2=next[k2%4][0];w2=next[k2%4][1];
}
else
{
p2=tx2;q2=ty2;
}
//printf("%d %d %d %d\n",p2,q2,p1,q1);
if(p1==p2&&q1==q2)//比较两个坐标是否相等
{
flag=1;break;
}
if(sum>50000)
break;
}
if(flag==1)
printf("%d\n",sum);
else
printf("0\n");
return 0;
}
