题解 P1518 【两只塔姆沃斯牛 The Tamworth Two】

· · 题解

这题的难度还是蛮大的，虽然这题很容易想到算法，但实际操作挺繁琐， 同p1098，好了废话不多说，上代码：

#include<bits/stdc++.h>
using namespace std;
bool a[160002];
int xx[4]={-1,0,1,0},yy[4]={0,1,0,-1},ans,x,y,f,g,ff,cf,s;
string st[12];
int main()
{
    int i,j; 
    for(i=0;i<10;i++)
            cin>>st[i]; //字符串直接单循环输入 
    for(i=0;i<10;i++)
        for(j=0;j<10;j++)
        {
            if(st[i][j]=='F')
            {
                x=i;
                y=j;
            }   
            if(st[i][j]=='C')
            {
                f=i;
                g=j;
            }       
        }
    while(1)
    {
        if(x==f&&y==g){
            cout<<ans;
            return 0;
        }
        s=x+y*10+f*100+g*1000+ff*10000+cf*40000;//标记
        if(a[s]==1)//如果JONE与奶牛不停地走重复的路就输出零
        {
            cout<<0;
            return 0;
        }
            a[s]=1;//每走一步就标记； 
        if(x+xx[ff]>=0&&x+xx[ff]<10&&y+yy[ff]>=0&&y+yy[ff]<10&&st[x+xx[ff]][y+yy[ff]]!='*')//小于10且前方不是障碍物 
        {
            x+=xx[ff];
            y+=yy[ff];
        }   
        else
            ff=(ff+1)%4;//否则转方向
        if(f+xx[cf]>=0&&f+xx[cf]<10&&g+yy[cf]>=0&&g+yy[cf]<10&&st[f+xx[cf]][g+yy[cf]]!='*')
        {
            f+=xx[cf];
            g+=yy[cf];
        }   
        else
            cf=(cf+1)%4;//奶牛同上
        ans++;              
    }
    return 0;
}