The Tamworth Two chapter 2.4

思路比较清楚,模拟+判断重复,定义好表示方式用位运算判重。

如何判重即是判断是否能相遇,记录每分钟时人和牛所在位置与行走方向,如果到某分钟时发现当前位置和方向已被记录过,则说明陷入循环

及永不会再相遇

  1 /*
  2 
  3 ID: hubiao cave
  4 
  5 PROG: ttwo
  6 
  7 LANG: C++
  8 
  9 */
 10 
 11 
 12 
 13 
 14 #include<iostream>
 15 
 16 #include<fstream>
 17 
 18 #include<string>
 19 
 20 using namespace std;
 21 
 22 
 23 int field[12][12];
 24 int record[120][120];
 25 int cs,ms;
 26 int cd=4,md=4;
 27 bool work();
 28 void cmwork(int&,int&);
 29 int minute;
 30 
 31 int main()
 32 
 33 {
 34 
 35     ifstream fin("ttwo.in");
 36 
 37     ofstream fout("ttwo.out");
 38     string str;
 39     for(int i=0;i<=9;++i)
 40     {
 41         fin>>str;
 42         for(int j=0;j<=9;++j)
 43         {
 44             if(str[j]=='*')
 45                 field[i][j]=16;
 46             else if (str[j]=='F')
 47             {
 48                 ms=10*i+j;
 49             }
 50             else if (str[j]=='C')
 51             {
 52                 cs=10*i+j;
 53             }
 54             else
 55                 ;
 56         }
 57 
 58         record[cs][ms]=(1<<(cd+3))+(1<<(md-1));
 59 
 60 
 61     }
 62 
 63     if(work())
 64             fout<<minute<<endl;
 65         else
 66             fout<<0<<endl;
 67     return 0;
 68 
 69 
 70 }
 71 
 72 bool work()
 73 {
 74     do
 75     {
 76         cmwork(cs,cd);
 77         cmwork(ms,md);
 78         ++minute;
 79         if(cs==ms)
 80             return true;
 81         else
 82         {
 83             if(record[cs][ms]&(1<<(3+cd))&&record[cs][ms]&(1<<(md-1)))
 84                 return false;
 85             else
 86                 record[cs][ms]+=1<<(3+cd)&&1<<(md-1);
 87         }
 88     }while(1);
 89 }
 90 
 91 void cmwork(int& xs,int&xd)
 92 {
 93     switch(xd)
 94     {
 95         case 1:
 96             if(xs%10==0||field[xs/10][xs%10-1]==16)
 97         {
 98             --xd;
 99             if(!xd)
100                 xd=4;    
101         }
102         else
103         {
104             xs=xs-1;
105         }
106             break;
107         case 2:
108             if(xs/10==9||field[xs/10+1][xs%10]==16)
109         {
110             --xd;
111             if(!xd)
112                 xd=4;    
113         }
114         else
115         {
116             xs=xs+10;
117         }
118             break;
119         case 3:
120           if(xs%10==9||field[xs/10][xs%10+1]==16)
121         {
122             --xd;
123             if(!xd)
124                 xd=4;    
125         }
126         else
127         {
128             xs=xs+1;
129         }
130 
131             break;
132         case 4:
133         if(xs/10==0||field[xs/10-1][xs%10]==16)
134         {
135             --xd;
136             if(!xd)
137                 xd=4;    
138         }
139         else
140         {
141             xs=xs-10;
142         }
143         
144             break;
145     }
146 }