This time your job is to fill a sequence of N positive integers into a spiral matrix in non-increasing order. A spiral matrix is filled in from the first element at the upper-left corner, then move in a clockwise spiral. The matrix has m rows and n columns, where m and n satisfy the following: m*n must be equal to N; m>=n; and m-n is the minimum of all the possible values.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N. Then the next line contains N positive integers to be filled into the spiral matrix. All the numbers are no more than 104. The numbers in a line are separated by spaces.
Output Specification:
For each test case, output the resulting matrix in m lines, each contains n numbers. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.
#include <stdio.h> #include <iostream> #include <algorithm> using namespace std; const int INF = 1000000000; const int maxv = 210; int N, m, n; int arr[10010] = {0};
bool cmp(int a, int b){ return a > b; } int main(){ //freopen("in.txt", "r", stdin); scanf("%d", &N); for(int i = 0; i < N; i++){ scanf("%d", &arr[i]); } int a, b, minDiff = INF; for(a = N; a > 0 ;a--){ if(N % a == 0){//可以整除 b = N / a; if(b > a) break; if(a - b < minDiff && a >= b){ minDiff = a - b; m = a; n = b; } } } sort(arr,arr+ N,cmp); int** matrix = new int*[m]; for(int i = 0; i < m ;i++){ matrix[i] = new int[n]; } for(int i = 0;i < m; i++){ for(int j = 0;j < n;j++){ matrix[i][j] = 0; } } int i = 0, x = 0, y = 0; while (i < N) { while (y < n&&!matrix[x][y]) matrix[x][y++] = arr[i++]; y--; x++; while (x < m && !matrix[x][y]) matrix[x++][y] = arr[i++]; x--; y--; while (y >= 0 && !matrix[x][y]) matrix[x][y--] = arr[i++]; y++; x--; while (x >= 0 && !matrix[x][y]) matrix[x--][y] = arr[i++]; x++; y++; } for(int i = 0;i < m; i++){ for(int j = 0;j < n;j++){ if(matrix[i][j]){ printf("%d", matrix[i][j]); if(j < n - 1) printf(" "); } } printf("n"); } return 0; }
近期评论