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

比眉伴天荒 2022-06-07 12:06 339阅读 0赞

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

上题目：

![Center][]

> 这是螺旋状的分布啊，有点像棒棒糖上面的圆圈圈。那么怎么解呢？
> 
> **一种思路：**先填外围一圈，然后把内部看作一个子问题，继续填充。
> 
> 即前面的4\*n-4个元素顺时针填充外围，
> 
> 剩下的问题变成用后面的元素填充一个规模为n-2的子问题。
> 
> 再用剩余元素的前面4\*(n-2)-4个元素顺时针填充规模为n-2的子问题外围，
> 
> 剩下的问题变成用后面的元素填充一个规模为n-4的更小的子问题
> 
> ……
> 
> 依次类推。
> 
> 当n=1时填唯一的一个数即可。
> 
> **换一种思路：**把放出一个好玩的贪吃蛇，按照右下左上的顺序吃蛋糕，一边吃蛋糕，一边拉数字，多吃一个蛋糕，拉出的数字多1，直到把所有的蛋糕吃完。

![Center 1][]

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

![Center 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;
> 
> 定义了偏移数组后，就可以从左上角开始，先向右走，只要有蛋糕或未到边界就继续前进，否则选择下一个方向，一直走下去，直到拉出的数字达到最大值*n*2，算法停止。
> 
> **那么你怎么知道有没有蛋糕呢？**
> 
> 因为吃了蛋糕后，这个方格就变成了一个大于零的数字，因此我们可以设置为0时有蛋糕。

![Center 3][]

> **那么你怎么知道有没有到达边界呢？**
> 
> 四周封锁：

![Center 4][]

> 做了封锁之后，小贪吃蛇再也不用担心跑出边界了，它只需要按照右下左上的方向，只吃有蛋糕的格子(为0)就可以了。
> 
> 源码：
> 
>     #include <iostream>
>     #include <algorithm>
>     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<<m[i][start];
>             for (int j=start+1; j<=endi; j++)
>             {
>                 cout<<"\t"<<m[i][j];
>             }
>             cout<<endl;
>         }
>         cout<<endl;
>     }
>      
>     // n：原问题规模
>     // m：地图矩阵
>     void Solve(int n)
>     {
>         here.x=1;//左上角有蛋糕的位置
>         here.y=1;
>         int dirIndex=0;
>         int num=1;
>         m[1][1]=1;
>         while(num<n*n)
>         {
>             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;//换下一个方向，按右下左上顺序继续吃蛋糕
>         }
>     }
>      
>      
>     int main()
>     {
>         int n=0;
>         cout<<"请输入大于1小于等于20的整数n:"<<endl;
>         cin>>n;
>         while(n<1||n>20)
>         {
>            cout<<"请输入大于1小于等于20的整数n:"<<endl;
>            cin>>n;
>         }
>         Init(n);
>         Print(0,n+1);
>         Solve(n);
>         Print(1,n);
>         return 0;
>     }
> 
>   
>   
>

[Center]: /images/20220607/ae9c5780776946468af93efbcdc64c3b.png
[Center 1]: /images/20220607/db9da376607b46608d0eae20f00dec93.png
[Center 2]: /images/20220607/96011d8ef9764f10b57aa45124afcc92.png
[Center 3]: /images/20220607/2d034921aa9248e8b26d8b4926a50cc5.png
[Center 4]: /images/20220607/2604b964a9164af3acdea8005eb5d706.png