PAT Basic Level 1050 螺旋矩阵 解题思路及AC代码_v0.8.1

本文主要是介绍PAT Basic Level 1050 螺旋矩阵 解题思路及AC代码_v0.8.1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目简述及在线测试位置

1.1 给定N个数，按非递增的顺序填入螺旋矩阵中（所谓螺旋矩阵，就是从左上角第1个数开始，按顺时针螺旋方向填充），螺旋矩阵的规模为 m 行 n 列（m×n=N；m≥n；m−n取所有可能值中的最小值）
1.2 在线测试位置： 1050 螺旋矩阵

2. 基本思路

2.0 螺旋矩阵示意图： 从外圈到内圈，按 从左到右、从上到下、从右到左、从下到上的顺序排列

2.1 需要解决三个问题：A. 将N个数字按非递增的顺序排列 B. 确定螺旋矩阵的行列数 C.将排序后的数字存储到螺旋矩阵中(二维数组)
2.2 问题A通过sort( )函数解决，compare( )要按非递增的顺序编写；问题B 根据条件 “Row × Column =N；Row ≥ Column ；Row − Column 取最小值” 编写代码即可

int ConfirmRow(int N)
{int Row = N, Column = 1, Balance = Row - Column;int Result = Row;while (Row * Row >= N){   //Row − Column 取最小值if (Row - Column < Balance && N % Row == 0){Column = N / Row;Balance = Row - Column;Result = Row;}Row--;}return Result;
}

2.3 对于问题C，需要按螺旋矩阵 从左到右、从上到下、从右到左、从下到上的顺序 将排序后的数字插入到二维数组中。注意边界位置数据的处理（方向转变处），对应代码中的 Up++, Right–, Down–, Left++

int Up = 0, Down = Row - 1, Left = 0, Right = Column - 1;
while (true){for (int i = Left; i <= Right; i++) //Left to Right{b[Up][i] = a[Count++];}if (Count >= N)break;Up++;for (int i = Up; i <= Down; i++) //Up to Down{b[i][Right] = a[Count++];}if (Count >= N)break;Right--;for (int i = Right; i >= Left; i--)//Right to Left{b[Down][i] = a[Count++];}if (Count >= N)break;Down--;for (int i = Down; i >= Up; i--)//Down to Up{b[i][Left] = a[Count++];}if (Count >= N)break;Left++;}

3. 完整AC代码

#include <algorithm>
#include <iostream> 
using namespace std;bool Compare(int a, int b)
{return a > b;
}int ConfirmRow(int N);void Insert_Sort(int a[], int N);int main()
{int N, Row, Column; //Row > Columncin >> N;int a[N], Count = 0;for (int i = 0; i < N; i++)cin >> a[i];sort(a, a + N, Compare);Row = ConfirmRow(N);Column = N / Row;int b[Row][Column];int Up = 0, Down = Row - 1, Left = 0, Right = Column - 1;while (true){for (int i = Left; i <= Right; i++) //Left to Right{b[Up][i] = a[Count++];}if (Count >= N)break;Up++;for (int i = Up; i <= Down; i++) //Up to Down{b[i][Right] = a[Count++];}if (Count >= N)break;Right--;for (int i = Right; i >= Left; i--)//Right to Left{b[Down][i] = a[Count++];}if (Count >= N)break;Down--;for (int i = Down; i >= Up; i--)//Down to Up{b[i][Left] = a[Count++];}if (Count >= N)break;Left++;}for (int i = 0; i < Row; i++){int j = 0;cout << b[i][j];for (j++; j < Column; j++){cout << " " << b[i][j];}cout << endl;}return 0;
}int ConfirmRow(int N)
{int Row = N, Column = 1, Balance = Row - Column;int Result = Row;while (Row * Row >= N){if (Row - Column < Balance && N % Row == 0){Column = N / Row;Balance = Row - Column;Result = Row;}Row--;}return Result;
}

这篇关于PAT Basic Level 1050 螺旋矩阵 解题思路及AC代码_v0.8.1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---