一只猫和一只老鼠在10*10的迷宫中。迷宫中的每个方格可以是空的，或者含有障碍。猫和老鼠可以进入任意一个空的方格中。当他们相遇时，猫和老鼠在同一个方格中。但是，无论猫或老鼠都不能进入有障碍的方格。我们可以用字符组成的二维数组表示迷宫，如下图所示。 老鼠在迷宫中按照一种固定的方式行走：每个时刻，老鼠都向它所面对的方向前进一格，这需要花费１秒时间。如果前方是一个障碍或者是迷宫的边界，它将花１秒的时间按顺时针方向转90度。为了抓到老鼠，这只猫决定也按照与老鼠相同的行走方式行进。猫和老鼠在每个单位时间内是同时行动的。因此，如果猫和老鼠在行进过程中“擦肩而过”，猫是无法捉到老鼠的。只有当猫和老鼠同时到达一个相同的格子时，猫才能捉住老鼠。 初始时，猫和老鼠不会在同一个方格中。并且它们都面向北方。你的任务是编一个程序，求出猫捉到老鼠的所花时间。 输入输出格式 输入数据的第一行n，表示输入数据的组数。每组数据由10行组成，每行10个字符，表示迷宫的地图以及猫和老鼠的初始位置。输入数据保证只有一只猫和一只老鼠。每组输入数据之后均有一个空行作为间隔。 对于每组给定的输入，输出一行仅含一个数，即猫捉到老鼠所花的时间。如果猫永远都无法抓到老鼠，则输出0。 样例输入1 *...*..... ......*... ...*...*.. .......... ...*.c.... *.....*... ...*...... ..m......* ...*.*.... .*.*...... 样例输出49/*C++版*/#include<iostream>using namespace std;struct NODE{ int row; //行    int line;//列};int main(){ char mapx[12][12]; int i,j,k,n,foot,mouse_dir,cat_dir; struct NODE cat,mouse;    cin>>n; for(i=0;i<n;i++) {  foot=0;//时间(步数)刚开始为0  //以下定义方向,1为北,2为东,3为南,4为西  mouse_dir=1;  cat_dir=1;  //输入地图  for(j=1;j<=10;j++)   for(k=1;k<=10;k++)   {    cin>>mapx[j][k];    if(mapx[j][k]=='m')      {       mouse.row=j;      mouse.line=k;     }       if(mapx[j][k]=='c')       {       cat.row=j;          cat.line=k;     }   }   //完善地图边界   for(j=0;j<12;j++)     {     mapx[j][0]='*';    mapx[j][11]='*';    mapx[0][j]='*';    mapx[11][j]='*';    }      while(foot<200)   {    if(mouse.row==cat.row&&mouse.line==cat.line)break;//猫捉到老鼠    else    {     switch(cat_dir)//猫的行进     {      //方面朝北     case 1:      {       if(mapx[cat.row-1][cat.line]=='*')cat_dir=2;       else cat.row--;       foot++;       break;      }      //方向朝东     case 2:      {       if(mapx[cat.row][cat.line+1]=='*')cat_dir=3;       else cat.line++;       foot++;       break;      }      //方向朝南     case 3:      {       if(mapx[cat.row+1][cat.line]=='*')cat_dir=4;       else cat.row++;       foot++;       break;      }      //方向朝西     case 4:      {       if(mapx[cat.row][cat.line-1]=='*')cat_dir=1;       else cat.line--;       foot++;       break;      }     }          switch(mouse_dir)//老鼠的行进     {      //方面朝北     case 1:      {       if(mapx[mouse.row-1][mouse.line]=='*')mouse_dir=2;       else mouse.row--;       break;      }      //方向朝东     case 2:      {       if(mapx[mouse.row][mouse.line+1]=='*')mouse_dir=3;       else mouse.line++;       break;      }      //方向朝南     case 3:      {       if(mapx[mouse.row+1][mouse.line]=='*')mouse_dir=4;       else mouse.row++;       break;      }      //方向朝西     case 4:      {       if(mapx[mouse.row][mouse.line-1]=='*')mouse_dir=1;       else mouse.line--;       break;      }     }    }   }   //猫捉到老鼠   if(foot<200)cout<<foot<<endl;   //猫永远抓不到老鼠   else cout<<"0"<<endl;  } return 0;} /*C语言版*/#include<stdio.h> struct NODE {   int two,one;  } ;  int main() {   char matrix[12][12];   int foot,i,k,j,n,cat_token,mouse_token;   struct NODE cat,mouse;   scanf("%d",&n);   getchar();   for(i=0;i<n;i++)    {         cat_token=1;     mouse_token=1;     foot=0;     for(j=1;j<=10;j++)      {       for(k=1;k<=10;k++)        {         scanf("%c",&matrix[j][k]);         if(matrix[j][k]=='m')          {           mouse.one=j;           mouse.two=k;          }         if(matrix[j][k]=='c')          {           cat.one=j;           cat.two=k;          }        }       getchar();      }     for(j=0;j<12;j++)      {       matrix[j][0]='*'; matrix[j][11]='*';       matrix[0][j]='*'; matrix[11][j]='*';      }         while(foot<200)      {       if(cat.one==mouse.one&&cat.two==mouse.two)         break;       else        {         switch(mouse_token)          {          case 1 :{           if(matrix[mouse.one-1][mouse.two]=='*')             mouse_token=2;           else             mouse.one--;           foot++;           break;            }          case 2 :{           if(matrix[mouse.one][mouse.two+1]=='*')             mouse_token=3;           else             mouse.two++;           foot++;           break;            }          case 3 :{           if(matrix[mouse.one+1][mouse.two]=='*')             mouse_token=4;           else             mouse.one++;           foot++;           break;            }          case 4 :{           if(matrix[mouse.one][mouse.two-1]=='*')             mouse_token=1;           else             mouse.two--;           foot++;           break;            }          }         switch(cat_token)          {          case 1 :{           if(matrix[cat.one-1][cat.two]=='*')             cat_token=2;           else             cat.one--;           break;            }          case 2 :{           if(matrix[cat.one][cat.two+1]=='*')             cat_token=3;           else             cat.two++;           break;            }          case 3 :{           if(matrix[cat.one+1][cat.two]=='*')             cat_token=4;           else             cat.one++;           break;            }          case 4 :{           if(matrix[cat.one][cat.two-1]=='*')        cat_token=1;      else       cat.two--;      break;       }     } } } if(foot<200)printf("%d\n",foot); else printf("0\n"); getchar(); } return 0; }

评论