数据结构第10讲好玩贪吃蛇——数字矩阵

冷不防 2022-05-17 13:41 180阅读 0赞

数据结构 第10讲 好玩贪吃蛇——数字矩阵

上题目：

![这里写图片描述][70]

这是螺旋状的分布啊，有点像棒棒糖上面的圆圈圈。那么怎么解呢？

一种思路：先填外围一圈，然后把内部看作一个子问题，继续填充。

即前面的4\*n-4个元素顺时针填充外围，

剩下的问题变成用后面的元素填充一个规模为n-2的子问题。

再用剩余元素的前面4\*(n-2)-4个元素顺时针填充规模为n-2的子问题外围，

剩下的问题变成用后面的元素填充一个规模为n-4的更小的子问题

……

依次类推。

当n=1时填唯一的一个数即可。

换一种思路：把放出一个好玩的贪吃蛇，按照右下左上的顺序吃蛋糕，一边吃蛋糕，一边拉数字，多吃一个蛋糕，拉出的数字多1，直到把所有的蛋糕吃完。

![这里写图片描述][70 1]

当贪吃蛇把小蛋糕吃完的时候，画风就变成了这样：

![这里写图片描述][70 2]

那么程序设计怎么做呢？

因为贪吃蛇出动按照右下左上四个方向，因此先定义一个方向偏移数组：

向右：行+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时有蛋糕。

![这里写图片描述][70 3]

那么你怎么知道有没有到达边界呢？

四周封锁：

![这里写图片描述][70 4]

做了封锁之后，小贪吃蛇再也不用担心跑出边界了，它只需要按照右下左上的方向，只吃有蛋糕的格子(为0)就可以了。

源码：

# include #

using namespace std;

typedef struct  
\{  
int x;  
int y;  
\} Position;//位置

int m\[30\]\[30\];//地图  
Position here,next;//当前位置，下一个位置  
Position DIR\[4\]=\{0, 1, 1, 0, 0, -1, -1, 0\};//右下左上方向数组

void Init(int n)  
\{  
for(int i=1; i<=n; i++)  
\{  
for(int j=1; j<=n; j++) //方格阵列初始化为0  
m\[i\]\[j\]=0;  
\}  
for(int j=0; j<=n+1; j++) //方格阵列上下围墙  
m\[0\]\[j\]=m\[n+1\]\[j\]=-1;  
for(int i=0; i<=n+1; i++) //方格阵列左右围墙  
m\[i\]\[0\]=m\[i\]\[n+1\]=-1;  
\}

void Print(int start,int endi)//start, endi为开始和结束下标  
\{  
for (int i=start; i<=endi; i++)  
\{  
cout<

[70]: /images/20220517/732c4d29278141918d22a858428b4f0c.png
[70 1]: /images/20220517/3ab77b0db0a14d338268cd0f4fbe3e94.png
[70 2]: /images/20220517/1518bb2326b042278b79da140f1548d5.png
[70 3]: /images/20220517/f719142f362c4409b84507b42c13298b.png
[70 4]: /images/20220517/cdb143246fd740a4aebb870cd102ca8e.png