上QQ阅读APP看书，第一时间看更新
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 }