洛谷P5731 蛇形方阵
|
4,459
|
题解
|
tdiant

给出一个不大于 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才对。

碰墙

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

首先，为了方便表示简化问题，在题目中这样的一个二维数组中，规定x和y的取值范围都是[1,n]，那么x和y都取不到0和n+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]);一直发现不出来）。唉！！！
希望自己之后能够细心一些吧！

上一篇
下一篇