The Tamworth Two

Leonx · 2022-09-17 21:59:41 · 个人记录

To solve this problem, using an simulating algorithm is easy to think of

• Create a Structure named P to store farmer's and cow's members

  In structure P , there are object's current coordinate(curx,cury) and direction

  Set a timer variable to zero and start simulating farmer 's and cow 's moving.

  • There are two condition for the end :

  1.1

  • when farmer and cow have the same coordinate at some time ,we can simply print the timer;

  • However ,how about the other condition where the farmer and cow can't reach to each other forever

  • On which occasion can we judge there won't be an encounter?

  1.2

  • The answer is that the same state occurs;
  • We can use a state function (6*variable ,involving farmer's and cow's coordinate and direction)

  For example:

  • we notice that

  • coordinate(curx,cury) in range(1,10)

  • direction in range (1,4)

  • define state funtion as

  • unsigned long long stateFunc(struct F,struct C)

  • {

  • return F.dir+C.dir10+F.curx100+F.cury10000+C.curx1000000+C.cury*100000000;

  • }

  • we use the discrete bytes in an (unsigned long long ) type to reprent differe state variables

  • So we can confirm that once two stateFuncs return the same value, the 1.2 condition occurs

  PS:

  notice that the timelimit is 1s we can use clock_t start and end as timer ,calculate the processing time; Once the time is longer than about 50ms, We can say that they can't encounter forever.

#include <iostream>
#include <string.h>
#include <cstring>
#include <time.h>
using namespace std;
char map[12][12];
/**
 * @brief solution
 * 
 * @author nileonx
 */
clock_t start = clock();
struct P
{
    /* data */
    string name;
    int direction;
    int curx,cury;
   // int inix,iniy;
    void initial(int x,int y)
    {
        this->curx=x;
        this->cury=y;
       // this->inix=x;
       // this->iniy=y;
        direction =0;
    }
   /* bool checkMyself()
    {
        if(direction!=1)
            return false;
        else if(curx==inix&&cury==iniy)
            return true;
        else 
            return false;
    }*/
    void move()
    {
      //  toString();
         direction%=4;
        switch(direction)
        {
            case 0:
                if(map[curx-1][cury]!='*'){curx--;}
                else direction++;
                break;
            case 1:
                if(map[curx][cury+1]!='*'){ cury++;}
                else direction++;
                break;
            case 2:
                if(map[curx+1][cury]!='*'){curx++;}
                else direction++;
                break;
            case 3:
                if(map[curx][cury-1]!='*'){cury--;}
                else direction++;
                break;
            //default:
              //  state++;
        }
    }
    bool equal(P another){return this->curx==another.curx&&this->cury==another.cury;}
    void toString()
    {
        cout<<name<<":\t{"<<direction<<" , "<<curx<<" , "<<cury<<" };\n";
    }

}cow,farmer;
int main()
{

    cow.name ="cow ";
    farmer.name = "farmer";
    memset(map,'*',sizeof(map));
    for(int i=1;i<=10;i++)
    {
         for(int j=1;j<=10;j++)
         {
            cin>>map[i][j];
            if(map[i][j]=='C')
            {
                cow.initial(i,j);
                //cout<<cow.curx<<" "<<cow.cury<<endl;
            }
            if(map[i][j]=='F')
            {
                farmer.initial(i,j);
            }
         }

        getchar();
    }
    //bool start =false;
    int time = 0; 

    while(true)
    {
        clock_t end= clock( );
       if(double(end-start)/CLOCKS_PER_SEC>0.05)
        {
            cout<<"0"<<endl;
            return 0;
        }

       // start =true;

        //cow's moving now

        cow.move();
        farmer.move();

        time++;
       // cout<<time<<endl;
      //  cout<<"Cow:\t"<<cow.curx<<"  "<<cow.cury<<endl;
      //  cout<<"Farmer:\t"<<farmer.curx<<"  "<<farmer.cury<<endl;
        if(cow.equal(farmer))
        {
            cout<<time<<endl;
            return 0;
        }
    }

    return 0;
}