本贴 包括，蛇行矩阵  蛇形填数  回形取数  等 蛇行系类（C语言详解）

 

                                         问题 1097: 蛇行矩阵

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

题目描述

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

输入

本题有多组数据，每组数据由一个正整数N组成。（N不大于100）

输出

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

样例输入

5

 

样例输出

1 3 6 10 15
2 5 9 14
4 8 13
7 12
11

提示

无

来源

无

 

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

如图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 型 ，内回环 外回环 等 后续再分析

 

 

扩展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;}