1.1.7　貓和老鼠

【例題講解】貓和老鼠（catmouse）

設“C”表示貓，“M”表示老鼠，“*”表示障礙，“.”表示空地。貓和老鼠在10×10的矩陣中，例如：

*...*.....

......*...

...*...*..

..........

...*.C....

*.....*...

...*......

..M......*

...*.*....

.*.*......

初始時貓和老鼠都面向北方（矩陣方向為上北下南、左西右東），它們每秒走一格，如果它們在同一格中，那么貓就抓住老鼠了（“對穿”是不算的）。貓和老鼠的移動方式相同：平時沿直線走，下一步如果會碰到障礙物或者出界，就用1秒的時間右轉90°。

試計算貓抓住老鼠需要多少秒。 

【輸入格式】

第1行為一個整數N（N≤10），表示有N組測試數據。 

每組測試數據為10行10列，格式如題目所描述。  

【輸出格式】

如果100步內無解，輸出-1，否則輸出貓抓住老鼠的時間。 

【輸入樣例】

1

*...*.....

......*...

...*...*..

..........

...*.C....

*.....*...

...*......

..M......*

...*.*....

.*.*......

【輸出樣例】

49

【算法分析】

設（x,y）為老鼠的坐標，（X,Y）為貓的坐標，0,1,2,3表示貓/老鼠移動的4個方向，每次按題目描述的移動方式更改老鼠和貓的坐標，直至兩者坐標重合或步數超過100步為止。

參考代碼如下。

 1  //貓和老鼠
 2  #include <bits/stdc++.h>
 3  using namespace std;
 4  
 5  int main()
 6  {
 7    int N,x,y,X,Y;                      //(x,y)為老鼠的坐標，(X,Y)為貓的坐標
 8    cin>>N;                                   
 9    for (int k = 0; k < N; k++)
 10    {
 11      int m=0,c=0,count=0;                    //m為貓的方向，c為老鼠的方向
 12      string Map[10];                         //儲存地圖
 13      for (int j = 0; j < 10; j++)
 14        cin>>Map[j];                          //一次讀一行
 15      for (int i = 0; i < 10; i++)            
 16        for (int j = 0; j < 10; j++)
 17          if (Map[i][j] == 'C')               //獲取貓所在的位置并標記
 18          {
 19            X = i;
 20            Y = j;
 21          }
 22          else if (Map[i][j] == 'M')          //獲取老鼠所在的位置并標記
 23          {
 24            x = i;
 25            y = j;
 26          }
 27      while (count < 100 && (X!=x || Y!=y))    //未到100步或未抓到則繼續
 28      {
 29        if (m==0 && x-1>=0 && Map[x-1][y]!='*')//模擬老鼠的移動
 30          x--;
 31        else if (m==1 && y+1<10 && Map[x][y+1]!='*')
 32          y++;
 33        else if (m==2 && x+1<10 && Map[x+1][y]!='*')
 34          x++;
 35        else if (m==3 && y-1>=0 && Map[x][y-1]!='*')
 36          y--;
 37        else
 38          m=(++m)%4;                            //改變方向
 39        if (c==0 && X-1>=0 && Map[X-1][Y]!='*') //模擬貓的移動
 40          X--;
 41        else if (c==1 && Y+1<10 && Map[X][Y+1]!='*')
 42          Y++;
 43        else if (c==2 && X+1<10 && Map[X+1][Y]!='*')
 44          X++;
 45        else if (c==3 && Y-1>=0 && Map[X][Y-1]!='*')
 46          Y--;
 47        else
 48          c=(++c)%4;                            //改變方向
 49        ++count;
 50      }
 51      printf("%d\n",(X == x && Y == y)?count:-1);
 52    }
 53    return 0;
 54  }