浙江财经大学
信工学院ACM集训队

FZU 1019 猫捉老鼠(模拟)

本文由 Ocrosoft 于 2016-12-02 17:30:31 发表

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Description

一只猫和一只老鼠在10*10的迷宫中。迷宫中的每个方格可以是空的,或者含有障碍。猫和老鼠可以进入任意一个空的方格中。当他们相遇时,猫和老鼠在同一个方格中。但是,无论猫或老鼠都不能进入有障碍的方格。我们可以用字符组成的二维数组表示迷宫,如下图所示。

老鼠在迷宫中按照一种固定的方式行走:每个时刻,老鼠都向它所面对的方向前进一格,这需要花费1秒时间。如果前方是一个障碍或者是迷宫的边界,它将花1秒的时间按顺时针方向转90度。
为了抓到老鼠,这只猫决定也按照与老鼠相同的行走方式行进。
猫和老鼠在每个单位时间内是同时行动的。因此,如果猫和老鼠在行进过程中“擦肩而过”,猫是无法捉到老鼠的。只有当猫和老鼠同时到达一个相同的格子时,猫才能捉住老鼠。 
初始时,猫和老鼠不会在同一个方格中。并且它们都面向北方。
你的任务是编一个程序,求出猫捉到老鼠的所花时间。

Input

输入数据的第一行n,表示输入数据的组数。 
每组数据由10行组成,每行10个字符,表示迷宫的地图以及猫和老鼠的初始位置。输入数据保证只有一只猫和一只老鼠。 
每组输入数据之后均有一个空行作为间隔。 

Output

对于每组给定的输入,输出一行仅含一个数,即猫捉到老鼠所花的时间。如果猫永远都无法抓到老鼠,则输出0。 

Sample Input

1
*...*.....
......*...
...*...*..
..........
...*.c....
*.....*...
...*......
..m......*
...*.*....
.*.*......

Sample Output

49

Solution

因为猫和老鼠的下一步动作都是固定的,没有偶然性,所以模拟着走,如果两者以相同的朝向回到了起始点,那么就捉不到;如果在这之前两者出现在同一个格子里,就能捉到;

还有一种不用记录状态的方法:如果猫和老鼠分别走完10000步,那么就是捉不到;这之前如果出现在同一个格子里,就能捉到; 
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define  rep(a,v,b) for(int a=v;a<b;a++)
#define  repe(a,v,b) for(int a=v;a<=b;a++)
typedef long long LL;
const int INF = INT_MAX / 2;
const int MAXN = 300000+ 10;
const int MOD = 1000000009;
int gcd(int a, int b)
{
	if (!b)return a;
	return gcd(b, a%b);
}
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕) 签订契约,成为马猴烧酒吧 (◕‿‿◕)*/
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
using namespace std;
char mp[12][12];
bool vis[12][12][12][12][5][5];
int cx,cy,mx,my,cd,md;
int main()
{
	int N;cin>>N;
	while(N--)
	{
		rep(i,0,10)cin>>mp[i];
		for(int i=0;i<10;i++)
		{
			for(int j=0;j<10;j++)
			{
				if(mp[i][j]=='c')cx=i,cy=j,cd=0;
				else if(mp[i][j]=='m')mx=i,my=j,md=0;
			}
		}
		vis[cx][cy][mx][my][cd][md]=1;
		bool flag=0;
		int time=0;
		while(1)
		{
			if(cx==mx&&cy==my)
			{
				flag=1;
				break;
			}
			switch (cd)
			{
			case 0:
				if(cx==0||mp[cx-1][cy]=='*')cd=1;
				else cx--;
				break;
			case 1:
				if(cy==9||mp[cx][cy+1]=='*')cd=2;
				else cy++;
				break;
			case 2:
				if(cx==9||mp[cx+1][cy]=='*')cd=3;
				else cx++;
				break;
			case 3:
				if(cy==0||mp[cx][cy-1]=='*')cd=0;
				else cy--;
				break;
			}
			switch (md)
			{
			case 0:
				if(mx==0||mp[mx-1][my]=='*')md=1;
				else mx--;
				break;
			case 1:
				if(my==9||mp[mx][my+1]=='*')md=2;
				else my++;
				break;
			case 2:
				if(mx==9||mp[mx+1][my]=='*')md=3;
				else mx++;
				break;
			case 3:
				if(my==0||mp[mx][my-1]=='*')md=0;
				else my--;
				break;
			}
			time++;
			if(cx==mx&&cy==my)
			{
				flag=1;
				break;
			}
			if(vis[cx][cy][mx][my][cd][md])break;
			else vis[cx][cy][mx][my][cd][md]=1;
		}
		if(flag)printf("%d\n",time);
		else printf("0\n");
	}
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » FZU 1019 猫捉老鼠(模拟)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址