Posts Tagged ‘C’

醉酒蟑螂的随机漫步

星期四, 6月 5th, 2008

C语言太久没碰，调试花了差不多一个晚上。程序编译环境：Fedora 8 gcc 4.1.2

在矩形房间里，地面铺有N＊M块瓷砖，一只醉酒的蟑螂在一块指定的瓷砖上随机漫步到相邻的令一块瓷砖上，求它至少接触每块瓷砖一次花费的时间。

实验按12*12的环境进行

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. //最大步数限制
  6. #define MAX_STEP_ON 65535
  7. #define MAX_X 12
  8. #define MAX_Y 12
  9.  
  10. //房间的磁砖
  11. unsigned arr[MAX_X][MAX_Y];
  12.  
  13. //相邻磁砖的位移
  14. const int stepx[]={-1,0,1,1,1,0,-1,-1};
  15. const int stepy[]={1,1,1,0,-1,-1,-1,0};
  16.  
  17. //记录当前位置
  18. int current[2];
  19.  
  20. //步数
  21. unsigned stepcount=0;
  22.  
  23. int main(){
  24. int isclean=clean();
  25. srand((unsigned)time(NULL));
  26. walk();
  27. }
  28.  
  29. int clean(){
  30. int x=0,y=0;
  31. for(x;x<MAX_X;x++){
  32. for(y;y<MAX_Y;y++){
  33. arr[x][y]=0;
  34. }
  35. }
  36. printf("please input the begin Abscissa\n");
  37. scanf("%d",&current[0]);
  38. printf("please input the begin Ordinate\n");
  39. scanf("%d",&current[1]);
  40. arr[current[0]][current[1]]+=1;
  41. return 1;
  42. }
  43.  
  44. int walk(){
  45. if(check()==0){
  46. int step=rand()%9;
  47. int nextx=current[0]+stepx[step];
  48. int nexty=current[1]+stepy[step];
  49. if(stepcount<MAX_STEP_ON){
  50. printinfo(0);
  51. exit(0);
  52. }
  53. if(nextx>=0&&nextx<=MAX_X-1&&nexty>=0&&nexty<=MAX_Y-1&&arr[nextx][nexty]<65535){
  54. ++arr[nextx][nexty];
  55. ++stepcount;
  56. //printf("%d,%d\t%d\n",current[0],current[1],step);
  57. current[0]=nextx;
  58. current[1]=nexty;
  59. }
  60. walk();
  61. }
  62. else{
  63. printinfo(1);
  64. exit(0);
  65. }
  66. }
  67.  
  68. int check(){
  69. int x,y;
  70. for(x=0;x<MAX_X;x++){
  71. for(y=0;y<MAX_Y;y++){
  72. if(arr[x][y]==0)
  73. return 0;
  74. }
  75. }
  76. return 1;
  77. }
  78.  
  79. int printinfo(int success){
  80. if(!success){
  81. printf("It's not Complete walk around the room\n");
  82. }
  83. printf("the bug total walk:%d steps\n\n",stepcount);
  84. int x,y;
  85. for(x=0;x<MAX_X;x++){
  86. for(y=0;y<MAX_Y;y++){
  87. if(y==0)
  88. printf("\n%d\t",arr[x][y]);
  89. else
  90. printf("%d\t",arr[x][y]);
  91. }
  92. }
  93. }

实验结果：

以下省略图N张

Tags: , ,
Posted in Technology | No Comments »