数据结构 第10讲 好玩贪吃蛇——数字矩阵
上题目：
这是螺旋状的分布啊，有点像棒棒糖上面的圆圈圈。那么怎么解呢？
一种思路：先填外围一圈，然后把内部看作一个子问题，继续填充。
即前面的4*n-4个元素顺时针填充外围，
剩下的问题变成用后面的元素填充一个规模为n-2的子问题。
再用剩余元素的前面4*(n-2)-4个元素顺时针填充规模为n-2的子问题外围，
剩下的问题变成用后面的元素填充一个规模为n-4的更小的子问题
……
依次类推。
当n=1时填唯一的一个数即可。
换一种思路：把放出一个好玩的贪吃蛇，按照右下左上的顺序吃蛋糕，一边吃蛋糕，一边拉数字，多吃一个蛋糕，拉出的数字多1，直到把所有的蛋糕吃完。
当贪吃蛇把小蛋糕吃完的时候，画风就变成了这样：
那么程序设计怎么做呢？
因为贪吃蛇出动按照右下左上四个方向，因此先定义一个方向偏移数组：
向右：行+0，列+1；偏移量：DIR[0].x=0; DIR[0].y=1;
向下：行+1，列+0；偏移量：DIR[1].x=1; DIR[1].y=0;
向左：行+0，列-1；偏移量：DIR[2].x=0; DIR[2].y=-1;
向上：行-1，列+0；偏移量：DIR[3].x=-1; DIR[3].y=0;
定义了偏移数组后，就可以从左上角开始，先向右走，只要有蛋糕或未到边界就继续前进，否则选择下一个方向，一直走下去，直到拉出的数字达到最大值n2，算法停止。
那么你怎么知道有没有蛋糕呢？
因为吃了蛋糕后，这个方格就变成了一个大于零的数字，因此我们可以设置为0时有蛋糕。
那么你怎么知道有没有到达边界呢？
四周封锁：
做了封锁之后，小贪吃蛇再也不用担心跑出边界了，它只需要按照右下左上的方向，只吃有蛋糕的格子(为0)就可以了。
源码：
[cpp]view plaincopy
#include
#include
usingnamespacestd;
typedefstruct
{
intx;
inty;
} Position;//位置
intm[30][30];//地图
Position here,next;//当前位置，下一个位置
Position DIR[4]={0, 1, 1, 0, 0, -1, -1, 0};//右下左上方向数组
voidInit(intn)
{
for(inti=1; i<=n; i++)
{
for(intj=1; j<=n; j++)//方格阵列初始化为0
m[i][j]=0;
}
for(intj=0; j<=n+1; j++)//方格阵列上下围墙
m[0][j]=m[n+1][j]=-1;
for(inti=0; i<=n+1; i++)//方格阵列左右围墙
m[i][0]=m[i][n+1]=-1;
}
voidPrint(intstart,intendi)//start, endi为开始和结束下标
{
for(inti=start; i<=endi; i++)
{
cout<
for(intj=start+1; j<=endi; j++)
{
cout<<"\t"<
}
cout<
}
cout<
}
// n：原问题规模
// m：地图矩阵
voidSolve(intn)
{
here.x=1;//左上角有蛋糕的位置
here.y=1;
intdirIndex=0;
intnum=1;
m[1][1]=1;
while(num
{
next.x=here.x+DIR[dirIndex].x;
next.y=here.y+DIR[dirIndex].y;
if(m[next.x][next.y]==0)//判断下一个位置是否有蛋糕
{
m[next.x][next.y]=++num;//吃了蛋糕，拉出的数字加1
here=next;//以next为当前位置，继续走
}
else
dirIndex=(dirIndex+1)%4;//换下一个方向，按右下左上顺序继续吃蛋糕
}
}
intmain()
{
intn=0;
cout<<"请输入大于1小于等于20的整数n:"<
cin>>n;
while(n<1||n>20)
{
cout<<"请输入大于1小于等于20的整数n:"<
cin>>n;
}
Init(n);
Print(0,n+1);
Solve(n);
Print(1,n);
return0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。博客原文地址http://blog.csdn.net/rainchxy/article/details/78296777
网友评论