洛谷P5731 蛇形方阵

给出一个不大于 9 的正整数 n,输出 n×n 的蛇形方阵。

从左上角填上 1 开始,顺时针方向依次填入数字,如同样例所示。注意每个数字有都会占用 3 个字符,前面使用空格补齐。

输入样例

4

输出样例

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

思路

这一个方阵可以看做一个二维数组,可以利用二维数组来储存各个位置上的数字。

x、y坐标的表示方法

习惯了行列式和矩阵的下标表示方式的话,应当知道i表示行,j表示列,这一规则在二维数组中也适用,如果有一个二维数组叫做nums,显然第i行第j列的元素应当是nums[i][j]

这完全可以从二维数组的本质来考虑。如果有一个这样的数组:

int example1[666];

显然example1是一个int类型的数组,其中的所有元都是int类型的数据。

那么如果有一个数组,它的所有元都是一个int类型的数组呢?也就是存在一个数组,其中的元存储的是数组,这种套娃便实现出了二维数组。
那基于这样的道理,二维数组是一个存着数组的数组,这个数组的元是各个行,那这个数组的标记便是行标了;每个元也都是数组,每个元的标记便是列标。

如果我把一个二维数组从几何的角度去观察,从左上角建立一个直角坐标系,右方是x的正方向,下方是y的正方向,那么怎样表示(x,y)这一点的元素呢?
答案并不是nums[x][y]而应当是nums[y][x],因为原先我们称之为行标的东西应当是这里的y,列标应当是x才对。

碰墙

填数问题最重要的思想就是“碰墙”了吧。

首先,为了方便表示简化问题,在题目中这样的一个二维数组中,规定xy的取值范围都是[1,n],那么xy都取不到0n+1才对。

我们的填数从(1,1)正式宣告开始!好了,首先它一直向右走,那它究竟什么时候才会停下来呢?
又是为了简化问题,再规定一下,nums数组中可以被填数的地方初始值都是0,如果不是0,那么就代表着它应当停下来,换一个方向了!

OK,现在我们为了让填的数字不会超出这个方阵的范围,我们在方阵最外一圈内造一个墙,这样就能迫使他只能拘禁在这个方阵内出不去了。

void initWall(){
    for (int i = 0; i <= n; ++i) {
        nums[0][i] = -1;
        nums[n + 1][i] = -1;
        nums[i][0] = -1;
        nums[i][n + 1] = -1;
    }
}

显然,这个墙会使得系统填到(1,n)准备往下走的时候,发现(1,n+1)不是0,系统便会停下来,换一个方向继续走。

方向变换

这道题中填数始终按照“右下左上”的顺序依次变换方向,还是为了简化问题,给这四个方向规定一个编号,用0代表右,1代表下、2代表左、3代表上,并且定义一个变量用来储存当前的方向。

int target = 0; //初始向右走

OK,现在方向确定完毕,那么如果它碰到了墙,想换方向咋办呢?
这也是为什么要这样定义方向的原因,因为可以用取模运算来代替一个if,下面这个函数就实现了换方向。

void turn() {
    target = (target + 1) % 4;
}

前进和撤回

万事俱备,现在可以让系统“向前走”了,这很简单,就像这样:

void move() {
    switch (target) {
        case 0:
            x += 1;
            break;
        case 1:
            y += 1;
            break;
        case 2:
            x -= 1;
            break;
        case 3:
            y -= 1;
            break;
    }
}

那如果系统(1,n)处走了一步发现,这里是墙,得“撤回来”,怎么办?我们反着写一个方法:

void undoMove() {
    switch (target) {
        case 0:
            x -= 1;
            break;
        case 1:
            y -= 1;
            break;
        case 2:
            x += 1;
            break;
        case 3:
            y += 1;
            break;
    }
}

其实这样有点傻,因为可以把1单独存一个变量,向前走这个变量是1,撤回那就是-1呗......

主逻辑的实现

大问题解决完毕,就只需要写出主逻辑即可:

    cin >> n;

    initWall();

    for (int i = 1; i <= n * n; ++i) {
        while (getNum() != 0) {
            undoMove();
            turn();
            move();
        }
        pushNum(i);
        move();
    }

最终代码

#include<iostream>
#include<cstdio>
using namespace std;

//0  right
//1  down
//2  left
//3  up

int nums[15][15]={0}, n, x=1, y = 1, target = 0;

void initWall();
void turn();
void move();
void undoMove();
int getNum();
void pushNum(int num);
void printA();

int main() {
    cin >> n;

    initWall();

    for (int i = 1; i <= n * n; ++i) {
        while (getNum() != 0) {
            undoMove();
            turn();
            move();
        }
        pushNum(i);
        move();
    }

    printA();

    return 0;
}

void initWall(){
    for (int i = 0; i <= n; ++i) {
        nums[0][i] = -1;
        nums[n + 1][i] = -1;
        nums[i][0] = -1;
        nums[i][n + 1] = -1;
    }
}

void turn() {
    target = (target + 1) % 4;
}

void move() {
    switch (target) {
        case 0:
            x += 1;
            break;
        case 1:
            y += 1;
            break;
        case 2:
            x -= 1;
            break;
        case 3:
            y -= 1;
            break;
    }
}

void undoMove() {
    switch (target) {
        case 0:
            x -= 1;
            break;
        case 1:
            y -= 1;
            break;
        case 2:
            x += 1;
            break;
        case 3:
            y += 1;
            break;
    }
}

int getNum() {
    return nums[y][x];
}

void pushNum(int num){
    nums[y][x] = num;
}

void printA() {
    for (int aY = 1; aY <= n; ++aY) {
        for (int aX = 1; aX <= n; ++aX) {
            printf("%3d", nums[aY][aX]);
        }
        cout<<endl;
    }
}

感想

这道题是一个很基础的二维数组操作题,但是自己在做的时候仍然错了很多次。
光是因为printf写错就WA了四五次(因为写成了printf("%3d 【这里多了一个空格】", nums[aY][aX]);一直发现不出来)。唉!!!
希望自己之后能够细心一些吧!

上一篇
下一篇