猫和老鼠 蓝桥杯／手速／暴力练习赛 【题目描述】 猫和老鼠在10*10 的方格中运动，例如： *...*..... ......*... ...*...*.. .......... ...*.C.... *.....*... ...*...... ..M......* ...*.*.... .*.*...... C=猫（CAT） M=老鼠（MOUSE） *=障碍物 .=空地 猫和老鼠每秒中走一格，如果在某一秒末他们在同一格中，我们称他们“相遇”。 注意，“对穿”是不算相遇的。猫和老鼠的移动方式相同：平时沿直线走，下一步如果会走到 障碍物上去或者出界，就用1 秒的时间做一个右转90 度。一开始他们都面向北方。 编程计算多少秒以后他们相遇。 【输入格式】 10 行，格式如上 【输出格式】 相遇时间T。如果无解，输出-1。 【样例输入】 *...*..... ......*... ...*...*.. .......... ...*.C.... *.....*... ...*...... ..M......* ...*.*.... .*.*......
1 /* 2 思路：如果猫和老鼠不相遇，那么一定是猫在某一个格子沿着某一个方向重复走了2次以上并且 3 老鼠也是这样。 4 */ 5 #include<iostream> 6 #include<cstring> 7 #include<cstdio> 8 #include<algorithm> 9 using namespace std; 10 11 char mp[15][15]; 12 13 const int left_dir = 1; 14 const int right_dir = 2; 15 const int up = 3; 16 const int down = 4; 17 const int mouse = 1; 18 const int cat = 0; 19 20 struct node{ 21 int x, y; 22 int dir; 23 node(){ 24 dir = up; 25 } 26 27 bool flag[15][15][5];//记录当前格子在某一个方向上是否走过 28 29 void init(int x, int y){ 30 memset(flag, false, sizeof(flag)); 31 this->x = x; 32 this->y = y; 33 flag[x][y][up] = true; 34 } 35 }; 36 37 node nd[2]; 38 int cnt = 0; 39 40 bool move(int i){ 41 int x=nd[i].x, y=nd[i].y; 42 int newdir; 43 switch(nd[i].dir){ 44 case up: 45 x-=1; 46 newdir = right_dir; 47 break; 48 case down: 49 x+=1; 50 newdir = left_dir; 51 break; 52 case left_dir: 53 y-=1; 54 newdir = up; 55 break; 56 case right_dir: 57 y+=1; 58 newdir = down; 59 break; 60 } 61 if(mp[x][y] != '*'){ 62 nd[i].x = x; 63 nd[i].y = y; 64 } else { 65 nd[i].dir = newdir; 66 } 67 68 if(!nd[i].flag[x][y][nd[i].dir]){ 69 nd[i].flag[x][y][nd[i].dir] = true; 70 return true; 71 } else return false; 72 } 73 74 void test(){ 75 bool flag = true, flag1=false, flag2=false; 76 while(flag){ 77 if(nd[cat].x == nd[mouse].x && nd[cat].y == nd[mouse].y) break; 78 if(!move(cat)) 79 flag1 = true; 80 if(!move(mouse)) 81 flag2 = true; 82 ++cnt; 83 if(flag1 && flag2) flag = false; 84 } 85 if(flag) printf("%d\n", cnt); 86 else printf("-1\n"); 87 } 88 89 int main() { 90 memset(mp, '*', sizeof(mp)); 91 for(int i=1; i<=10; ++i){ 92 scanf("%s", mp[i]+1); 93 mp[i][strlen(mp[i]+1)+1] = '*'; 94 for(int j=1; j<=10; ++j){ 95 if(mp[i][j]=='C'){ 96 nd[cat].init(i, j); 97 mp[i][j] = '.'; 98 } 99 else if(mp[i][j] == 'M'){ 100 nd[mouse].init(i, j); 101 mp[i][j] = '.'; 102 } 103 } 104 getchar(); 105 } 106 test(); 107 return 0; 108 } 109 /* 110 *...*..... 111 ......*... 112 ...*...*.. 113 .......... 114 ...*.C.... 115 *.....*... 116 ...*...... 117 ..M......* 118 ...*.*.... 119 .*.*...... 120 */
