作者在 2011-03-11 15:46:44 发布以下内容
猫捉老鼠一只猫和一只老鼠在10*10的迷宫中。迷宫中的每个方格可以是空的，或者含有障碍。猫和老鼠可以进入任意一个空的方格中。当他们相遇时，猫和老鼠在同一个方格中。但是，无论猫或老鼠都不能进入有障碍的方格。我们可以用字符组成的二维数组表示迷宫，如下图所示。
老鼠在迷宫中按照一种固定的方式行走：每个时刻，老鼠都向它所面对的方向前进一格，这需要花费１秒时间。如果前方是一个障碍或者是迷宫的边界，它将花１秒的时间按顺时针方向转90度。
为了抓到老鼠，这只猫决定也按照与老鼠相同的行走方式行进。
猫和老鼠在每个单位时间内是同时行动的。因此，如果猫和老鼠在行进过程中“擦肩而过”，猫是无法捉到老鼠的。只有当猫和老鼠同时到达一个相同的格子时，猫才能捉住老鼠。
初始时，猫和老鼠不会在同一个方格中。并且它们都面向北方。
你的任务是编一个程序，求出猫捉到老鼠的所花时间。
初始时，猫和老鼠不会在同一个方格中。并且它们都面向北方。
你的任务是编一个程序，求出猫捉到老鼠的所花时间。
输入输出格式
输入数据的第一行n，表示输入数据的组数。
每组数据由10行组成，每行10个字符，表示迷宫的地图以及猫和老鼠的初始位置。输入数据保证只有一只猫和一只老鼠。
每组输入数据之后均有一个空行作为间隔。
对于每组给定的输入，输出一行仅含一个数，即猫捉到老鼠所花的时间。如果猫永远都无法抓到老鼠，则输出0。
每组数据由10行组成，每行10个字符，表示迷宫的地图以及猫和老鼠的初始位置。输入数据保证只有一只猫和一只老鼠。
每组输入数据之后均有一个空行作为间隔。
对于每组给定的输入，输出一行仅含一个数，即猫捉到老鼠所花的时间。如果猫永远都无法抓到老鼠，则输出0。
样例输入
1
*...*.....
......*...
...*...*..
..........
...*.c....
*.....*...
...*......
..m......*
...*.*....
.*.*......
*...*.....
......*...
...*...*..
..........
...*.c....
*.....*...
...*......
..m......*
...*.*....
.*.*......
样例输出
49
--------------------------------------------
评论人: laisszhun 发布时间: 2008-7-4 12:49:57#include "stdio.h"
void main()
{
char mi_g[10][11];
int i,j,a,b,c,d;
int zhuo_ls(char mi_g[10][11],int a,int b,int c,int d);
printf("请输入迷宫的图形：\n");
for(i=0;i<10;i++)
gets(mi_g[i]);
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{
if(mi_g[i][j]=='c')
{
a=i;
b=j;
}
if(mi_g[i][j]=='m')
{
c=i;
d=j;
}
}
printf("\n需要使用时间：%d",zhuo_ls(mi_g,a,b,c,d));
}
int zhuo_ls(char mi_g[10][11],int a,int b,int c,int d)
{
int sum=0,e=0,f=0,g=0,h=0,i=0,j=0,k=0,l=0;
int ji_l[10][10][8]={0};
char fang_x[4]={'n','e','s','w'}; /* 4个方向 */
char *p_m=fang_x,*p_c=fang_x;
while(a!=c||b!=d)
{
switch(*p_m)
{
case 'n': if(ji_l[a][b][0]==0)
ji_l[a][b][0]=1;
else if(e++>100) goto loop;
if((a-1)>=0&&mi_g[a-1][b]!='*')
a=a-1;
else p_m++;
break;
case 'e': if(ji_l[a][b][1]==0)
ji_l[a][b][1]=1;
else if(f++>100) goto loop;
if((b+1)<10&&mi_g[a][b+1]!='*')
b=b+1;
else p_m++;
break;
case 's': if(ji_l[a][b][2]==0)
ji_l[a][b][2]=1;
else if(g++>100) goto loop;
if((a+1)<10&&mi_g[a+1][b]!='*')
a=a+1;
else p_m++;
break;
case 'w': if(ji_l[a][b][3]==0)
ji_l[a][b][3]=1;
else if(h++>100) goto loop;
if((b-1)>=0&&mi_g[a][b-1]!='*')
b=b-1;
else p_m=fang_x;
break;
}
switch(*p_c)
{
case 'n': if(ji_l[c][d][0]==0)
ji_l[c][d][0]=1;
else if(i++>100) goto loop;
if((c-1)>=0&&mi_g[c-1][d]!='*')
c=c-1;
else p_c++;
sum++;
break;
case 'e': if(ji_l[c][d][1]==0)
ji_l[c][d][1]=1;
else if(j++>100) goto loop;
if((d+1)<10&&mi_g[c][d+1]!='*')
d=d+1;
else p_c++;
sum++;
break;
case 's': if(ji_l[c][d][2]==0)
ji_l[c][d][2]=1;
else if(k++>100) goto loop;
if((c+1)<10&&mi_g[c+1][d]!='*')
c=c+1;
else p_c++;
sum++;
break;
case 'w': if(ji_l[c][d][3]==0)
ji_l[c][d][3]=1;
else if(l++>100) goto loop;
if((d-1)>=0&&mi_g[c][d-1]!='*')
d=d-1;
else p_c=fang_x;
sum++;
break;
}
}
return sum;
loop:
return 0;
}
用C写的。。处女帖~谢谢
评论人: Yimi_flowers 发布时间: 2008-6-20 22:04:30有没有更HIGH一点的吖
这个太罗嗦了..
评论人: zxcv1220 发布时间: 2008-5-23 10:39:43#include <stdio.h>
#include <stdlib.h>
void main()
{
int zhuiji(char e[][11],int a,int b);
int zhuiji1(char e[][11],int a,int b,int m,int n);
char e[10][11];
int a,b,i;
printf("请出入迷宫图形\n");
for(i=0;i<10;i++)
{
gets(e[i]);
}
printf("请出入老鼠位置:\n");
scanf("%d%d",&a,&b);
printf("%d\n",zhuiji(e,a,b));
system("pause");
}
int zhuiji1(char e[][11],int a,int b,int t,int m,int n)
{
int num1=1,p=1,q=0;
while(p<=t+1)
{
p++;
if(q==t)
{
if(a==m&&b==n)
{
return 1;
break;
}
else
{
return 0;
}
}
if(num1==1)
{
if(e[m-1][n]!='/'&&m!=0)
{
q++;
m=m-1;
continue;
}
else
{
q++;
num1=2;
continue;
}
}
else if(num1==2)
{
if(e[m][n+1]!='/'&&n!=9)
{
q++;
n=n+1;
continue;
}
else
{
q++;
num1=3;
continue;
}
else if(num1==2)
{
if(e[m][n+1]!='/'&&n!=9)
{
q++;
n=n+1;
continue;
}
else
{
q++;
num1=3;
continue;
}
}
else if(num1==3)
{
if(e[m+1][n]!='/'&&m!=9)
{
q++;
m=m+1;
continue;
}
else
{
q++;
num1=4;
continue;
}
}
{
if(e[m+1][n]!='/'&&m!=9)
{
q++;
m=m+1;
continue;
}
else
{
q++;
num1=4;
continue;
}
}
else if(num1==4)
{
if(e[m][n-1]!='/'&&n!=0)
{
q++;
n=n-1;
continue;
}
else
{
q++;
num1=1;
continue;
}
}
}
p=1;
}
int zhuiji(char e[][11],int a,int b)
{
int t=0,num=1,k=100,m,n;
printf("请输入猫的位置：\n");
scanf("%d%d",&m,&n);
while(k>0)
{
k--;
if(zhuiji1(e,a,b,t,m,n))
{
return t;
break;
}
if(num==1)
{
if(e[a-1][b]!='/'&&a!=0)
{
t++;
a=a-1;
continue;
}
else
{
t++;
num=2;
continue;
}
{
if(e[m][n-1]!='/'&&n!=0)
{
q++;
n=n-1;
continue;
}
else
{
q++;
num1=1;
continue;
}
}
}
p=1;
}
int zhuiji(char e[][11],int a,int b)
{
int t=0,num=1,k=100,m,n;
printf("请输入猫的位置：\n");
scanf("%d%d",&m,&n);
while(k>0)
{
k--;
if(zhuiji1(e,a,b,t,m,n))
{
return t;
break;
}
if(num==1)
{
if(e[a-1][b]!='/'&&a!=0)
{
t++;
a=a-1;
continue;
}
else
{
t++;
num=2;
continue;
}
}
else if(num==2)
{
if(e[a][b+1]!='/'&&b!=9)
{
t++;
b=b+1;
continue;
}
else
{
t++;
num=3;
continue;
}
else if(num==2)
{
if(e[a][b+1]!='/'&&b!=9)
{
t++;
b=b+1;
continue;
}
else
{
t++;
num=3;
continue;
}
}
else if(num==3)
{
if(e[a+1][b]!='/'&&a!=9)
{
t++;
a=a+1;
continue;
}
else
{
t++;
num=4;
continue;
}
}
{
if(e[a+1][b]!='/'&&a!=9)
{
t++;
a=a+1;
continue;
}
else
{
t++;
num=4;
continue;
}
}
else if(num==4)
{
if(e[a][b-1]!='/'&&b!=0)
{
t++;
b=b-1;
continue;
}
else
{
t++;
num=1;
continue;
}
}
}
}
{
if(e[a][b-1]!='/'&&b!=0)
{
t++;
b=b-1;
continue;
}
else
{
t++;
num=1;
continue;
}
}
}
}