﻿FZU 1019 猫捉老鼠(模拟)-Ocrosoft

# FZU 1019 猫捉老鼠(模拟)

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

Description

Input

Output

Sample Input

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

Sample Output

49

Solution

#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;
}