某训练

某训练

猫和老鼠

【题目描述】

猫和老鼠在10*10 的方格中运动，例如：
 *...*.....
 ......*...
 ...*...*..
 ..........
 ...*.C....
 *.....*...
 ...*......
 ..M......*
 ...*.*....
 .*.*......
 C=猫（CAT）
 M=老鼠（MOUSE）
 *=障碍物
 .=空地
 猫和老鼠每秒中走一格，如果在某一秒末他们在同一格中，我们称他们“相遇”。
 注意，“对穿”是不算相遇的。猫和老鼠的移动方式相同：平时沿直线走，下一步如果会走到
 障碍物上去或者出界，就用1 秒的时间做一个右转90 度。一开始他们都面向北方。
 编程计算多少秒以后他们相遇。

【输入格式】

10 行，格式如上

【输出格式】

相遇时间T。如果无解，输出-1。

【样例输入】

*...*...........*......*...*...............*.C....*.....*......*........M......*...*.*.....*.*......

【样例输出】

49

AC代码：

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#define LL long long
#define INF 0x7fffffff
using namespace std;char map[15][15]; 
int cx, cy, mx, my;//分别代表猫和老鼠的位置 
int xx[4] = {-1, 0, 1, 0};//方向 
int yy[4] = {0, 1, 0, -1};//方向 
int cdir, mdir;//分别代表猫和老鼠的朝向 int judge() {		//判断当前是否相遇 if(cx == mx && cy == my) return 1;return 0;
}int main() {for(int i = 1; i <= 10; i++) {scanf("%s", map[i] + 1);}for(int i = 1; i <= 10; i++) {for(int j = 1; j <= 10; j++) {if(map[i][j] == 'C') {cx = i; cy = j;}if(map[i][j] == 'M') {mx = i; my = j;}}}//printf("%d %d %d %d n", cx, cy, mx, my);int ans = 0;cdir = 0; mdir = 0;while(1) {//while(1) {if(map[cx + xx[cdir]][cy + yy[cdir]] != '*' && cx + xx[cdir] <= 10 && cx + xx[cdir] >= 1 && cy + yy[cdir] <= 10 && cy + yy[cdir] >= 1) {cx = cx + xx[cdir]; cy = cy + yy[cdir];//break;}else cdir = (cdir + 1) % 4;//}//while(1) {if(map[mx + xx[mdir]][my + yy[mdir]] != '*' && mx + xx[mdir] <= 10 && mx + xx[mdir] >= 1 && my + yy[mdir] <= 10 && my + yy[mdir] >= 1) {mx = mx + xx[mdir]; my = my + yy[mdir];//break;}else mdir = (mdir + 1) % 4;//}ans ++;if(ans >= 100000) break; //用于判断是否可以相遇，这么大点地方100000应该够了，虽然有偶然性 if(judge()) break;}if(ans == 100000) printf("-1n");else printf("%dn", ans);return 0;
}