写点什么

蛇行矩阵 蛇形填数 回形取数 蛇行系类(C 语言详解 + 图解)

作者:Five
  • 2022 年 8 月 24 日
    四川
  • 本文字数:2489 字

    阅读完需:约 8 分钟

蛇行矩阵 蛇形填数 回形取数 蛇行系类(C语言详解+图解)

本文 包括,蛇行矩阵  蛇形填数  回形取数  等 蛇行系类(C 语言详解)

❓问题描述


                                         问题 1097: 蛇行矩阵

时间限制: 1Sec 内存限制: 64MB 提交: 1979 解决: 1164

题目描述

蛇形矩阵是由 1 开始的自然数依次排列成的一个矩阵上三角形。

输入

本题有多组数据,每组数据由一个正整数 N 组成。(N 不大于 100)

输出

对于每一组数据,输出一个 N 行的蛇形矩阵。两组输出之间不要额外的空行。矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。

样例输入

5


样例输出

1 3 6 10 152 5 9 144 8 137 1211

提示

来源

💡思路

观察即可  这类题 主要是找规律 找找关联

如图 a 观察 可得 每一组斜线数据 从起点到终点 都是从小到大排列 因此我们只需要让上一个终点可以到下一个起点,就可以了,怎么找 加上坐标如图 b 再看 所有的起点和终点关于 对角线对称所有的终点之间就差一个单位 (就是说 上一个终点(x,y) 和下一个终点(x,y++)差一个单位  y ++ 即可,而起点 和终点 关于对角线对称  所以终点(x,y) 他对应的起点则是(y,x))。这样 就让上一个终点通过关系 到下一个起点了。

当然 方法很多 ,这只是个人理解。


图a


图b


下面是实现代码:


#include<stdio.h>int main(){    int  n;    while(~scanf("%d", &n)){      int a[110][110]={0};//初始化       int i=1,tn=n,x=0,y=0;      // i代表 需要填的数值 tn循环的次数 x,y 起点坐标      while(tn--){         while(x>=0&&y<n)a[x--][y++]=i++;        // 边界跳出条件  循环填数 x-- y++ 就代表 按左下到右上的对角线移动填数         x++;//刚跳出边界的x肯定变成-1了 因此要回溯下回到终点 y不用回 因为本来就要y++         int tem=x;x=y;y=tem;// 将终点变为起点  交换坐标      }    for(x=0;x<n;x++){//打印 上三角 图形       for(y=0;y<n-x;y++)         printf("%d ",a[x][y]);        printf("\n");    }  }    return 0;}
复制代码


 扩展

 此类题 还可以扩展成各类蛇行方式的题 比如  S 型 ,内回环 外回环 等 


S型


内回环型


外回环型


扩展 1 蛇形填数:

             

问题 1796: 蛇形填数

时间限制: 1Sec 内存限制: 128MB 提交: 298 解决: 68

题目描述

在 n * n 方阵里填入 1, 2, …, n * n, 要求填成蛇形。例如 n = 4 时方阵为: 10 11 12 1 9 16 13 2 8 15 14 3 7  6  5 4

输入

多组测试数据。每组测试数据第一行输入方阵的维数,即 n 的值。(n <= 100)

输出

每组测试数据输出结果是蛇形方阵,方阵中每行每两个元素间空格,末尾不要有多余空格,每个方阵后空一行。

样例输入

3


样例输出

7 8 1 
6 9 2 
5 4 3


💡思路

感觉有点 dfs 的感觉 不装南墙不变方向 这里南墙指的 方阵的边界或前进方向的格子里面有数填进去了。

正题, 就是在执行下一步之前先预判一下当前你想到的下一个格子是否在方阵范围内是否有数已经填进去了。 只有 在方阵内 并且 格子里面没有被填过 则可以移动到格子里填数。下面是代码 不多 可以阅读下 理理思路。

  AC 代码

#include<stdio.h>int main(){    int n;    while(~scanf("%d",&n)){        int x=0,y=n-1,num=1;int a[100][100]={0};        a[x][y]=num++;//初始坐标        while(n*n>=num) {//结束条件            while(x+1<n&&!a[x+1][y])a[++x][y]=num++;//向下            while(y-1>=0&&!a[x][y-1])a[x][--y]=num++;//向左            while(x-1>=0&&!a[x-1][y])a[--x][y]=num++;//向上            while(y+1<n&&!a[x][y+1])a[x][++y]=num++;//向右        }        for(x=0;x<n;x++) {          for (y=0;y<n;y++)           if(y==n-1) printf("%d",a[x][y]);//注意题目要求 末尾没空格           else  printf("%d ",a[x][y]);            printf("\n");        }         printf("\n");//注意题目要求 每个方阵空行    }    return 0;}
复制代码


扩展 2:[蓝桥杯][基础练习 VIP]回形取数


                                        [蓝桥杯][基础练习 VIP]回形取数

时间限制: 1Sec 内存限制: 128MB 提交: 254 解决: 66

题目描述

回形取数就是沿矩阵的边取数,若当前方向上无数可取或已经取过,则左转 90 度。一开始位于矩阵左上角,方向向下。

输入

输入第一行是两个不超过 200 的正整数 m,  n,表示矩阵的行和列。接下来 m 行每行 n 个整数,表示这个矩阵。

输出

输出只有一行,共 mn 个数,为输入矩阵回形取数得到的结果。数之间用一个空格分隔,行末不要有多余的空格。

样例输入

3  3 

1  2  3 

4  5  6 

7  8  9 

样例输出

1 4 7 8 9 6 3 2 5


💡思路

      和蛇形填数 类似 不过填变成取了, 不装南墙不变方向 这里南墙指的 方阵的边界或前进方向的格子里面有数被加上标记了。(此题标记可以不要 只需要 令取了的格子赋值为 1 即可,这里是为了保险起见 题目没有明说数据范围,我们不能妄加判断,万一卡了啦 )


正题, 就是在执行下一步之前先预判一下当前你想到的下一个格子是否在方阵范围内是否有被取走了里面的数。 只有 在方阵内 并且 格子里面没有被取过 则可以移动到格子里取数。下面是代码 不多 可以阅读下 理理思路。


AC 代码:

#include<stdio.h>#include<string.h> int main(){     int n,m,x,y,num;int a[210][210];int f[210][210];//f[][] 标记     while(scanf("%d%d",&n,&m)!=EOF){       memset(f,0,sizeof(f));       for(x=0;x<n;x++)        for(y=0;y<m;y++)       scanf("%d",&a[x][y]);       num=1;x=0;y=0;       printf("%d",a[x][y]);f[x][y]=1;//初始首位       while(n*m>num){           while(x+1<n&&!f[x+1][y])printf(" %d",a[++x][y]),f[x][y]=1,num++;//向下           while(y+1<m&&!f[x][y+1])printf(" %d",a[x][++y]),f[x][y]=1,num++;//向右           while(x-1>=0&&!f[x-1][y])printf(" %d",a[--x][y]),f[x][y]=1,num++;//向上           while(y-1>=0&&!f[x][y-1])printf(" %d",a[x][--y]),f[x][y]=1,num++;//向右       }       printf("\n");//末尾空行     }return 0;}
复制代码


发布于: 刚刚阅读数: 4
用户头像

Five

关注

有事多研究,没事瞎琢磨 2022.08.02 加入

第三季签约作者 ,CSDN 前端领域优质创作者 , 博客专家认证, 华为云云享专家。 退役ACMer, IT技术狂热爱好者 擅长领域,web前端,算法, 业务架构,可视化,富文本编辑器等。 github: https://github.com/Five-great

评论

发布
暂无评论
蛇行矩阵 蛇形填数 回形取数 蛇行系类(C语言详解+图解)_c_Five_InfoQ写作社区