【题目02】蛇形矩阵（snake.cpp）wikioi1160
蛇形矩阵是一种御防性极强的魔法阵，其关键是讲魔法力最强的学员放在魔法阵的最里面，用数学方法来表示，即为取n行n列数字矩阵（其中n为不超过100的奇数），在矩阵中心从1开始以逆时针方向绕行，逐圈扩大，直到n行n列填满数字，如图所示为3行3列的蛇形矩阵，请输出该n行n列正方形矩阵以及矩阵对角线数字之和。
【输入格式】：
一个整数n（即n行n列）
【输出格式】：
n+1行,n行为组成的矩阵，最后一行为对角线数字之和。
【输入样例】：
3
【输出样例】：
5 4 3
6 1 2
7 8 9
25

#include<bits/stdc++.h> 
using namespace std;
int main(){
    int n,x,y;
    cin>>n;
    x=(n+1)/2,y=(n+1)/2;
    int a[50][50];
    int sx=1,num=1;
    a[x][y]=num;
    while(num<n*n) {
        num++;
        y++;
        a[x][y]=num;
        while(x>n/2-sx) {x--;num++;a[x][y]=num;}
        while(y>n/2-sx) {y--;num++;a[x][y]=num;}
        while(x<n/2+sx) {x++;num++;a[x][y]=num;}
        while(y>n/2+sx) {y++;num++;a[x][y]=num;}
        sx++;
    }
    y++;
    a[x][y]=num;
    for(register int i=1;i<=n;i++)
     {
         for(register int j=1;j<=n;j++)
          cout<<a[i][j]<<" ";
          cout<<endl;
     }
    return 0;
}

首先以3为例，模拟一下数组的移动方向

    int n, x, y;
    cin >> n;
    x = y = (n) / 2;
    int a[50][50]{{ 0 }};
    int sx = 1, num = 1;
    a[x][y] = num;
    while (num<n*n)
    {
        a[x][++y] = ++num;
        a[--x][y] = ++num;
        a[x][--y] = ++num;
        a[x][--y] = ++num;
        a[++x][y] = ++num;
        a[++x][y] = ++num;
        a[x][++y] = ++num;
        a[x][++y] = ++num;
    }

    for (register int i = 0; i < n; i++)
    {
        for (register int j = 0; j < n; j++)
            cout << a[i][j] << " ";
        cout << endl;
    }

接着开始归纳

    int n, x, y;
    cin >> n;
    x = y = (n) / 2;
    int a[50][50]{{ 0 }};
    int sx = 1, num = 1;
    a[x][y] = num;
    while (num<n*n)
    {
        a[x][++y] = ++num;
        a[--x][y] = ++num;
        a[x][--y] = ++num;
        a[x][--y] = ++num;
        a[++x][y] = ++num;
        a[++x][y] = ++num;
        while (++y<n)
        a[x][y] = ++num;
        //a[x][++y] = ++num;
    }

    for (register int i = 0; i < n; i++)
    {
        for (register int j = 0; j < n; j++)
            cout << a[i][j] << " ";
        cout << endl;
    }

运行无错后把能归纳的都归纳

    int n, x, y;
    cin >> n;
    x = y = (n) / 2;
    int a[50][50]{{ 0 }};
    int sx = 1, num = 1;
    a[x][y] = num;
    while (num<n*n)
    {
        a[x][++y] = ++num;
        a[--x][y] = ++num;
        while (--y>=0)
            a[x][y] = ++num; ++y;
        while (++x<n)
            a[x][y] = ++num; --x;
        while (++y<n)
            a[x][y] = ++num; --y;
    }

    for (register int i = 0; i < n; i++)
    {
        for (register int j = 0; j < n; j++)
            cout << a[i][j] << " ";
        cout << endl;
    }

这样慢慢调试

[此贴子已经被作者于2020-3-1 17:08编辑过]

按照你的思路，应该是while里面套着一些if的结构，确保每次循环只有一个num++能够执行得到。
而不是while套着while

另外，从外面倒着转进来其实简单一些。

谢谢！！

[此贴子已经被作者于2020-3-2 03:51编辑过]

最后优化一下代码，再弄一个旋转方向。

[此贴子已经被作者于2020-3-2 04:25编辑过]

这叫螺旋矩阵吧，蛇形矩阵不是走斜线的那种吗？
运行了下楼主的代码，部分值显示为未初始化，应该是算法有问题。
这个题我记得以往我也是用数组解决的，还称其为“行程开关”算法，但我记得那次跟帖的一个高人是用纯数学计算解决的，可惜已经找不到那个贴了，百度了下，也没找到相关公式。不过我仍然想到一个不用数组的解决方法，只是效率较低：

#include <stdio.h>
int spiral(int n,int l)
{
    int i=0,sum=1,step=1,x0,y0,s,f[4][2]={-1,0,0,1,1,0,0,-1};
    x0=y0=(int)n/2;
    while (sum<=n*n)
    {
        s=0;
        while(s<step)
        {
            if(x0==l%n&&y0==l/n)return sum;
            x0+=f[i][0];
            y0+=f[i][1];
            sum++;
            s++;
        }
        i++;
        if(i&&!(i%2))step++;
        if(i>3)i=0;
    }
    return 0;
}

void main()
{
    int i,n=15;
    if(n<3||!(n%2))n=3;
    for(i=0;i<n*n;i++)
    {
        if(i&&!(i%n))printf("\n");
        printf("%5d",spiral(n,i));
    }
    printf("\n");
}

之前写过不用数组的由外而内，其实由内而外也是一样道理。

https://blog.bccn.net/xianfajushi/66997