|
- UID
- 852722
|
这是个经典的数学问题，说的是：在一个随机的迷宫里，小白鼠如何能最快地从起点走到终点。
-# --------### # ## # # ###
----# # #-## # # # #### #### #
#### #-# ## # # # #---# ## #
## # # # # -# ### ## #### ##
# # ----# # # ## # # # ## ### ##
-# --# ---### -* # ## # # ###
----# # #-## # # -----### #### #
#### #-# ## # # # #---# ## #
## # # # # -# ### ## #### ##
# # ----# # # ## # # # ## ### ##
按上图，老鼠用“*”来表示，要求从迷宫的左上脚选择一条路径，跑道右下脚的出口。也许用神经网络、用遗传算法之类能找到一个最佳的做法，但我这个程序是基于对迷宫完全无知，而且没有试验的这个前提，所以我只能采用最机械的办法：每条路都试探。具体是这样的：向左看看，能否过去。只要左面不是墙，就走到出一步。若左面不能过去，看下面，再看右面...若三个方向都不能过去，只能回到上一步，重复干...
程序并不长，但它在四年前费了我一个星期的所有时间（包括上课 :-)）。一直在我磁盘里放着，不拿出来分享，怪可惜的。你看看能不能找到更好的办法？望交流。
注释一：你能看见迷宫几乎完全是随机的，但为了保证一定有一条通道，我在起点和终点附近各放了九个可以通行的点。不算作弊吧。
注释二：循环里面的延时对于PENTIUM几乎一点作用都没有。所以运行时你或者选用 STEP，或者把延时提高一点，才能看清小白鼠是如何迈向前途未卜的新一步，又是如何迷途知返，重新审视自己的步伐。
注释三：这个程序的技巧很好，但完全没有注释，风格也不太好，但这正是几年前我的标准的程序，所以现在我也不改，直接拿出来，仅供一娱。
注释四：程序用TC才能编译。VC，标准C中没有“gotoxy”等函数。当然，这只影响界面显示，不影响我们老鼠行走的算法。
您还可以直接下载已编译好的程序maze.exe
--------------------------------------------------------------------------------
源程序如下：
#include < stdlib.h>
#include < time.h>
#include < stdio.h>
#include < conio.h>
main()
{int x,y,a[72][22];
charo;
intc,d,four,k=0,i,end,step;
randomize();
/* printf("Do you want it run orstep?(0/1)");
scanf("%d",&step);*/
clrscr();
for(x=0;x < 72;x++){
for (y=0;y < 22;y++){
if ((y==0)||(x==0)||(x==71)||(y==21)) {
a[x][y]=11;
continue;}
if (random(3)==0) {
a[x][y]=11;
gotoxy(x,y);
printf("#");
}
else
a[x][y]=1;
}
}
for(y=1;y < 10;y++)
{a[1][y]=1;
gotoxy(1,y);
printf(" ");
a[70][21-y]=1;
gotoxy(70,21-y);
printf(" ");
}
x=1;
y=1;
end=0;
gotoxy(1, 23);
printf("Step?(1/0) ");scanf("%d",&step);
//Above is to prepare the Maze. Now, ourlittle mouse is comming.
while((x < 70)||(y < 20))
{
c=x;d=y;four=0;
do{
k++;
if((a[x+1][y]==1)||((a[x+1][y]%7==0)&&(a[x][y]%2!=0)&&(four==1)))
{
a[x][y]=a[x][y]*2;
x=x+1;
break;
}
if((a[x][y+1]==1)||((a[x][y+1]%5==0)&&(a[x][y]%3!=0)&&(four==1)))
{
a[x][y]=a[x][y]*3;
y=y+1;
break;
}
if((a[x][y-1]==1)||((a[x][y-1]%3==0)&&(a[x][y]%5!=0)&&(four==1)))
{
a[x][y]=a[x][y]*5;
y=y-1;
break;}
if((a[x-1][y]==1)||((a[x-1][y]%2==0)&&(a[x][y]%7!=0)&&(four==1)))
{a[x][y]=a[x][y]*7;
x=x-1;
break;
}
four++;
if (four == 2){
gotoxy(25, 23); printf("Cannot go out!");
end=1;
break;}
if (k>3000) {
gotoxy(30, 23); printf("Too long!");
end=1;
break;}
}while(1);
if (end==1) break;
/* gotoxy(x,y);printf("*");*/
gotoxy(c,d);printf("-");
gotoxy(16, 23); printf("step:%d ", k);
gotoxy(x,y); printf("*");
if (step==1) getch();
}/*no end point*/
if(end==1) printf("Error.");
elseprintf("ok!");
getch();
}/*end main()*/
看懂程序了吗？当时我发现必须用一些东西来记录老鼠的历史，即要知道在该点是否已经向右走过？是否向左走过？用了4天脑袋里跳出“素数”这样一个悠久的名词，于是一切就水到渠成了！
在Do-While中的第一个if的意思是：如果右边的方格是如果从未走过的空地（值为1），走过去。但是，如果上下左右都没有值为1的空地，就必须考虑退路了。这时four==1，查看一下我是否已经走过这个地方 (a[x][y]%2!=0)？我是否从那里过来的(a[x+1][y]%7==0)？也就是说当four==4时我只走回头路。
你的程序会采取这种策略吗？ |
|
