1050. 螺旋矩阵(25)

原题: https://www.patest.cn/contests/pat-b-practise/1050

没错思路(之一)

而是参考了简书OliverLew大神的思绪, 才搞出来的.

该题正确的思路解法可分为3部分
1) 确定宽高, 对原始数组进行排序
2) 对数组原始数组进行螺旋遍历, 得到矩阵数组
3) 控制打印变量

一旦高为h, 宽为w, 已了解h * w = n, h >= w足汲取
h * h >= n, 因此我们仅仅待让i从1上马添加, 检测
i * i >= n && n % i == 0 由于要求h - w最小,
因而首先不善极建立时即淡出循环

接下最要的即是怎对矩阵展开螺旋遍历, 看下图题目中
被的测试

0 1 2
3 4 5
6 7 8
9 10 11

咱俩要之行是
0 1 2 5 8 11 10 9 6 3 4 7

可以看任意一点的坐标都是当下左右坐标加上w倍的总宽度.
比如5 = 2 + 1 * 3, 11 = 2 + 3 * 3, 现在单纯待另外新建两独变量
分别代表可变的丰饶高, 比如测试用例中高=4, 宽等3, 首先为右侧走, 走至
终极, 往生移动, 这个时候高度减去1, 同理往生活动及首要还往左走, 这个时刻
增幅减去1

个体考虑

用到问题本身大约就是是管题目分成三片, 1, 确定宽高, 2,
把正常数组变成矩阵数组, 3, 简单打印出来.

第一会规定的是自然使先期排序, 直接用C语言自带的qsort, 接着极美好
的方案便会寻找打只公式把例行排好序的数组和用的矩阵数组下标给
相应起来, 研究了一半上, 最终发现找不交其他规律! 接着我又将问题中让
的测试数据的下标给写了下, 如下

0 1 2
3 4 5
6 7 8
9 10 11

这时节我忽然想到了好原先开了之”老鼠活动迷宫”那道题, 好像得移植了
来行使, 只要确定了开始坐标, 老鼠每次活动按照”右下左上”的原理运动, 走过
的路标记为0, 这样经过老鼠所走之门径就可知把我们需要的矩阵数组拿到. 正
备兴致冲冲的开写, 结果发现边界问题无法确定, 要惦记了解啊时候遇到墙要
老是都知当前的坐标, 因此又卡主了.

自己平开始算宽高的思路也比低级, 我是一个个遍历每次计算宽高的差值从而
最后确定宽高.

实现

#include <stdio.h>
#include <stdlib.h> // 定义qsort
#define LEN 10010

int compare (const void *a, const void *b);

int main (void) {
    int n;
    int height;   // 高
    int width;    // 宽
    int src[LEN]; // 原始数组
    int i;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &src[i]);
    }
    // 计算宽高
    for (i = 1; i <= n; i++) {
        if (i * i >= n && n % i == 0) {
            height = i;
            width = n / i;
            break;
        }
    }
    // 对原始数组进行递减排序
    qsort(src, n, sizeof(int), compare);

    int matrix[LEN]; // 矩阵
    int w = width;   // 可变宽
    int h = height;  // 可变高
    int x = -1;      // 初始x位置
    int y = 0;       // 初始y位置
    int len = 0;     // 矩阵长度

    while (w > 0 && h > 0) {
        /*
            在这里给大家分析下, 为什么每次需要保证h > 0, 或者
            w > 0. 如果没有这两个保证, 将只能得到21分, 有2个  
            测试点过不去.
            假如现在只剩下最后一行, 假设高为1, 宽为6, 这个时候
            我们走到终点, 整个矩阵遍历就结束了, 但此时的下一步
            往下走也就是高减去1为0, 而宽还是6. 因为高为0了, 所以
            向下不会走也就是不动, 但是再接着往左走, 这个时候因为  
            宽不为0, 还会接着遍历, 这就出问题了. 因此每次都必须
            要检测h > 0 或者 w > 0
        */

        // 向右
        for (i = 0; i < w && h > 0; i++) {
            x++;
            matrix[x + y * width] = src[len++];
        }
        h--; // 这里也可以 if (h == 0) break; 下同理
        // 向下
        for (i = 0; i < h && w > 0; i++) {
            y++;
            matrix[x + y * width] = src[len++];
        }
        w--;
        // 向左
        for (i = 0; i < w && h > 0; i++) {
            x--;
            matrix[x + y * width] = src[len++];
        }
        h--;
        // 向上
        for (i = 0; i < h && w > 0; i++) {
            y--;
            matrix[x + y * width] = src[len++];
        }
        w--;
    }
    // 打印
    char ch;
    for (i = 0; i < len; i++) {
        if ((i + 1) % width == 0) {
            ch = '\n';
        } else {
            ch = ' ';
        }
        printf("%d%c", matrix[i], ch);
    }

    return 0;
}

int compare (const void *a, const void *b) {
    int arg1 = *(int*)a;
    int arg2 = *(int*)b;
    return arg2 - arg1;
}

参考: OliverLew http://www.jianshu.com/p/f79c413e1dbd