最近在浏览自己的博客时发现之前发布的走迷宫问题中，在创建迷宫数组模块可能会导致时间消耗较大。所以就想了一下如何优化的问题。之前的代码如下：
1 void creat_arr(int a[][N]) //创建迷宫数组 2 { 3 int i,j,x,y,tem,m=0,k[100]; 4 bool flag; 5 srand(time(0)); 6 for(i=0;i<N;i++) 7 for(j=0;j<N;j++) 8 a[i][j]=2; 9 for(i=0;i<(N-2)*(N-2)*(0.9-0.4*M);i++) //当难度系数为0.5时，空格数占0.7；当难度系数为1时，空格数占0.5 10 { 11 flag=false; 12 x=rand()%(N-2)+1; 13 y=rand()%(N-2)+1; 14 tem=x*10+y; 15 for(j=0;j<m;j++) 16 { 17 if(tem==k[j]) 18 { 19 flag=true; 20 break; 21 } 22 } 23 if(flag) 24 { 25 i--; 26 } 27 else 28 { 29 k[m++]=tem; 30 a[x][y]=0; 31 } 32 } 33 }
我们可以看一下上面的代码，可能会导致的问题是：当数组k[]中数据足够多时，由于x,y不确定性，可能会使tem命中率大幅下降，从而拖慢了整个代码的运行。那么如何使随机数据确定化呢？我想到的是将上面的过程反过来，我们先产生随机的两位数，然后将其分解为x,y。这样有一个好处是，我们可以先不考虑二维数组的创建，将主要的思路集中在生成随机两位数上。换句换说，我们只需将确定的两位数打乱，然后选取其中的多少个做为空格数即可。
下面是优化过后的代码：
1 void creat_arr(int a[][N]) //创建迷宫数组 2 { 3 int i,j,x,y; 4 int tem[(N-2)*(N-2)]; //临时数组 5 int k=(int)((N-2)*(N-2)*(0.9-0.4*M)); //难度系数 6 srand(time(0)); 7 x=(N-2)*(N-2); 8 for(i=0;i<x;i++) 9 { 10 tem[i]=(i/8+1)*N+1+i%8; //tem数组初始值为11-18,21-28,31-38,……,81-88 11 } 12 for(i=0;i<k;i++) 13 { 14 int t; 15 y=rand()%(x-i)+i; //随机生成一个i至x-1间的数据，并将tem[y]与tem[i]交换 16 t=tem[y]; 17 tem[y]=tem[i]; 18 tem[i]=t; 19 } 20 for(i=0;i<N;i++) 21 for(j=0;j<N;j++) 22 a[i][j]=2; 23 for(i=0;i<k;i++) 24 { 25 int m,n; 26 m=tem[i]/10; 27 n=tem[i]%10; 28 a[m][n]=0; 29 } 30 }
我们先用一个临时的一位数组来存储11-18,21-28,……,81-88数据，然后根据空格数将数据打乱，选取前多少转换m,n即可。