fuzhuo-----Problem 1019 猫捉老鼠

秒速五厘米 2022-06-15 08:37 113阅读 0赞

## Problem Description ##

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

![1019.gif][]

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

## ![prodesc.gif][] Input ##

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

## ![prodesc.gif][] Output ##

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

## ![prodesc.gif][] Sample Input ##

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

## ![prodesc.gif][] Sample Output ##

#include<cstdio>
    struct point
    {
        int x,y;
    };
    char ai[10][11];
    void move(point &a,int &f)//模拟，注意加上地址符号，因为要改变数值
    {
        switch(f)
        {
        case 1:
            if(ai[a.x-1][a.y]=='.')
                a.x-=1;
            else
                f=4;
            break;
        case 2:
            if (ai[a.x][a.y-1]=='.')
                a.y-=1;
            else
                f=1;
            break;
        case 3:
            if (ai[a.x+1][a.y]=='.')
                a.x+=1;
            else
                f=2;
            break;
        case 4:
            if (ai[a.x][a.y+1]=='.')
                a.y+=1;
            else
                f=3;
            break;
        }
    }
    int main()
    {
        int n,i,j,time,cf,mf;
        point c,m;
        scanf("%d",&n);
        while(n--)
        {
            time=0;
            cf=1;
            mf=1;
            for (i=0; i<10; i++)
                scanf("%s",ai[i]);
            for (i=0; i<10; i++)
            {
                for (j=0; j<10; j++)
                {
                    if (ai[i][j]=='c')
                    {
                        ai[i][j]='.';
                        c.x=i;
                        c.y=j;
                    }
                    else if (ai[i][j]=='m')
                    {
                        ai[i][j]='.';
                        m.x=i;
                        m.y=j;
                    }
                }
            }
            while(1)
            {
                time++;
                if(time>10000)//走了超过10000步
                {
                    printf("0\n");
                    break;
                }
                move(c,cf);//这里是每次走一步就跳出
                move(m,mf);
                if(c.x==m.x&&c.y==m.y)
                {
                    printf("%d\n",time);
                    break;
                }
            }
        }
        return 0;
    }

[1019.gif]: http://acm.fzu.edu.cn/image/Problem/1019.gif
[prodesc.gif]: http://acm.fzu.edu.cn/image/prodesc.gif