[USACO2.4] 两只塔姆沃斯牛 The Tamworth Two
题目描述
两只牛逃跑到了森林里。Farmer John 开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为（牛和 John）。
追击在 10 × 10 10 \times 10 10×10 的平面网格内进行。一个格子可以是：一个障碍物，两头牛（它们总在一起），或者 Farmer John。两头牛和 Farmer John 可以在同一个格子内（当他们相遇时），但是他们都不能进入有障碍的格子。
一个格子可以是：
.空地；*障碍物；C两头牛；FFarmer John。
这里有一个地图的例子：
*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......
牛在地图里以固定的方式游荡。每分钟，它们可以向前移动或是转弯。如果前方无障碍（地图边沿也是障碍），它们会按照原来的方向前进一步。否则它们会用这一分钟顺时针转 90 度。 同时，它们不会离开地图。
Farmer John 深知牛的移动方法，他也这么移动。
每次（每分钟）Farmer John 和两头牛的移动是同时的。如果他们在移动的时候穿过对方，但是没有在同一格相遇，我们不认为他们相遇了。当他们在某分钟末在某格子相遇，那么追捕结束。
读入十行表示地图。每行都只包含 10 个字符，表示的含义和上面所说的相同。保证地图中只有一个 F 和一个 C。F 和 C 一开始不会处于同一个格子中。
计算 Farmer John 需要多少分钟来抓住他的牛，假设牛和 Farmer John 一开始的行动方向都是正北（即上）。 如果 John 和牛永远不会相遇，输出 0。
输入格式
输入共十行，每行 10 个字符，表示如上文描述的地图。
输出格式
输出一个数字，表示 John 需要多少时间才能抓住牛们。如果 John 无法抓住牛，则输出 0。
样例 #1
样例输入 #1
*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......
样例输出 #1
49
提示
翻译来自NOCOW
USACO 2.4
借鉴的代码：主要用了特征值判重
刚刚好每个数值不超过10，即数位上的最大值
#include<cstdio>
bool zt[160005];//10*10*10*10*4*4=160000，开大一点以防万一
char mp[11][11];
int cx,cy,cf,fx,fy,ff,xx[4]={-1,0,1,0},yy[4]={0,1,0,-1},nt,stp;
int main()
{
for(int i=0;i<10;i++)
scanf("%s",mp[i]);//读入
for(int i=0;i<10;i++)
for(int j=0;j<10;j++)
{
if(mp[i][j]=='F')//遇到农夫
fx=i,fy=j;//设定初始坐标
if(mp[i][j]=='C')//遇到牛
cx=i,cy=j;//设定初始坐标
}
while(1)
{
if(fx==cx&&fy==cy)//相遇了
{
printf("%d",stp);//输出步数
return 0;//退出
}
nt=fx+fy*10+cx*100+cy*1000+ff*10000+cf*40000;//生成特征值
if(zt[nt])//如果出现过了，则无解
{
printf("0");
return 0;
}
zt[nt]=1;//保存特征值
if(fx+xx[ff]<0||fx+xx[ff]>=10||fy+yy[ff]<0||fy+yy[ff]>=10||mp[fx+xx[ff]][fy+yy[ff]]=='*')//判断农夫是否还能向前走
ff=(ff+1)%4;//如果不行，转向
else fx=fx+xx[ff],fy=fy+yy[ff];//否则继续向前
if(cx+xx[cf]<0||cx+xx[cf]>=10||cy+yy[cf]<0||cy+yy[cf]>=10||mp[cx+xx[cf]][cy+yy[cf]]=='*')//判断牛是否还能向前走
cf=(cf+1)%4;//如果不行，转向
else cx=cx+xx[cf],cy=cy+yy[cf];//否则继续向前
stp++;//增加步数
}
return 0;
}
lose’s work
#include <iostream>
#include <string>
#include <map>
using namespace std;
int dir[4] = {0,1,2,3}; //分别表示上，右，下，左 顺时针
int go[4][2] = {1,0,0,1,-1,0,0,-1};//与上面相对应
//录入的行数依次递减，即最下方是第一行
int FX,FY,CX,CY; //FC的位置
int FD=0,CD=0; //方向
int map1[10][10] = {0}; //地图 0:不可行 1：可行
typedef struct node
{//包含方向才能准确判重
int fx,fy,cx,cy;
int dirF,dirC;
node(int Fx,int Fy,int Cx,int Cy,int Df,int Dc)
:fx(Fx),fy(Fy),cx(Cx),cy(Cy),dirF(Df),dirC(Dc){}
}point;
struct cmp
{
bool operator()(struct node const &a, struct node const &b) const //自定义排序
{
int sum1 = a.fx+a.fy*10+
return a.fx<b.fx;
}
};
map<point,bool,cmp> mp;//结合两者来判断是否能抓到牛
bool judge(int x,int y)
{
if((x<0)||(x>9)||(y<0)||(y>9))//越界
return false;
if(map1[x][y] == 0) //不可通
return false;
}
int main()
{
//读入地图数据
for(int i=9;i>=0;i--)
{
string a;
cin>>a;
for(int j=0;j<10;j++)
{
if(a[j] == '*') map1[i][j] = 0;
else if(a[j] == 'F')
{
FX = i;FY = j;
map1[i][j] = 1;
}
else if(a[j] == 'C')
{
CX = i;CY = j;
map1[i][j] = 1;
}
else
{
map1[i][j] = 1;
}
}
}
int ans=-1; //循环开始时+1，表示当前的时间
//进行模拟
while(1)
{
ans++;
//移动牛
int x,y;//下一步的预定位置
x = CX+go[CD][0];
y = CY+go[CD][1];
if(judge(x,y) == false) //转向
{system("pause");
while(judge(x,y) == false)
{
CD = (CD+1)%4;
x = CX+go[CD][0];
y = CY+go[CD][1];
}
}
else
{
//直接赋值
CX = x;
CY = y;
}
//移动农场主
x = FX+go[FD][0];
y = FY+go[FD][1];
if(judge(x,y) == false) //转向
{
while(judge(x,y) == false)
{
FD = (FD+1)%4;
x = FX+go[FD][0];
y = FY+go[FD][1];
}
}
else
{
//直接赋值
FX = x;
FY = y;
}
cout<<" F"<<FX<<" "<<FY<<" "<<FD<<endl;
cout<<" C"<<CX<<" "<<CY<<" "<<CD<<endl<<endl;
//判断场面是否重复、是否抓住
if(mp.count(point(FX,FY,CX,CY,FD,CD)) == 0) //未重复
{cout<<"1111"<<endl;
mp.insert(map<point,bool>::value_type(point(FX,FY,CX,CY,FD,CD),true));
}
else
{cout<<point(FX,FY,CX,CY,FD,CD).dirF<<endl;
ans = 0;
break;
}
if((FX == CX)&&(FY == CY)) break;//成功抓捕
}
cout<<ans;
return 0;
}
map仅对自定义排序所用来比较的元素进行排序，而与结构体中的其他元素无关。而普通map不允许有重复元素，所以尽管其他值不一样，用于排序的值一样就进不去map
还是替换了原来的？
或许可以把状态（坐标、方向）转化成字符串存储在map中查找
