1105 Spiral Matrix (25 分)
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 1. 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.
- Sample Input:
- 12
- 37 76 20 98 76 42 53 95 60 81 58 93
- Sample Output:
- 98 95 93
- 42 37 81
- 53 20 76
- 58 60 76
题意:
用这个数列的数, 形成一个螺旋矩阵 (顺时针) 从大到小
题解:
1. 将数列排序
2. 分别填入向右向下向左向上四个方向的数字, 一次控制 列坐标增加, 行坐标增加, 列坐标减少, 行坐标减少.
AC 代码:
- #include<bits/stdc++.h>
- using namespace std;
- int N;
- int a[100005];
- int n,m;
- int ma[105][105];
- int main(){
- memset(a,0,sizeof(a));
- cin>>N;
- for(int i=1;i<=N;i++) cin>>a[i];
- sort(a+1,a+1+N);
- for(int i=1;i<=sqrt(N);i++){
- if(N%i==0){
- m=i;
- n=N/i;
- }
- }
- //cout<<n<<" "<<m<<endl;
- int x=0,y=1;
- int d=1;
- for(int i=N;i>=1;i--){
- if(d==1){
- x++;
- if(x>m||ma[y][x]!=0){
- d=2;
- x--;
- y++;
- }
- }else if(d==2){
- y++;
- if(y>n||ma[y][x]!=0){
- d=3;
- y--;
- x--;
- }
- }else if(d==3){
- x--;
- if(x<1||ma[y][x]!=0){
- d=4;
- x++;
- y--;
- }
- }else{
- y--;
- if(y<1||ma[y][x]!=0){
- d=1;
- y++;
- x++;
- }
- }
- ma[y][x]=a[i];
- }
- for(int i=1;i<=n;i++){
- for(int j=1;j<=m;j++){
- cout<<ma[i][j];
- if(j!=m) cout<<" ";
- else cout<<endl;
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3395263.html