某训练 - 猫和老鼠 - 模拟

猫和老鼠

【题目描述】

猫和老鼠在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("-1\n");
	else printf("%d\n", ans);
	return 0;
}

某训练 - 猫和老鼠 - 模拟

原文：http://blog.csdn.net/u014355480/article/details/44876875