P1518 题解

beacon_cwk · 2018-07-21 13:50:15 · 题解

这题没有什么坑点，主要问题是判断他们是否能够相遇。一种做法是在移动次数达到一定值时判定为无法相遇，但还有另一种思路：给每个状态设定一个值，如果这个值之前已经出现过，说明他们陷入了循环，不能相遇。每个状态都要保存农夫和牛的x、y坐标（各10种可能）和方向（各4种可能），其中为了避免重复，可以将特征值设为

可以用bool数组来实现以O(1)的复杂度来查询该值是否已经出现。

代码：

#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;
}