PAT Advanced 1105 Spiral Matrix

Overview

PAT advanced 1105 Spiral Matrix can be solved by first sorting the numbers and then recursively print the sorted list in the spiral matrix.

PAT Advenced 1105 Spiral Matrix Problem

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.

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

PAT Advenced 1105 Spiral Matrix Algorithm

This problem tests 3 aspects:

  1. sorting, this is easy, using STL
  2. figure out the row and columns such that row * column == n and row >= clumn, this is math problem
  3. two dimentional array index manupilation, that is, map the elements from one dimensional vector into a two dimensional array by spiral order (clockwise). It is easier to understand and achive the solution recursively, essentially, we need 4 print, print it into the top row, print the numbers in the right column, print the numbers in the bottom row, print the numbers in the left column, and then the problem is reduced into the same 4 pass printing with a smaller number of rows and columns.

The following C++ code is accepted by PAT OJ to pass this 1105 Spiral matrix using the algorithm above:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <utility>
#include <vector>

using std::pair;
using std::vector;
using std::sqrt;

pair<long, long> getRowColumn(long n) {
	long r = (long) sqrt(n);

	while (r < n && 
                     (r < n / r || n % r != 0)) {
		++r;
	}
	return std::make_pair(r, n / r);
}


void gao(const vector<int> &vec,
		int k, 
		vector<vector<int>> &result,
		int i, 
		int r, int c) { 

	if (r < 1 || c < 1) {
		return;
	}

	if (1 == r) {
		for (int j = 0; j < c; ++j) {
			result[i][i+j] = vec[k++];
		}
		return;
	}

	if (1 == c) {
		for (int j = 0; j < r; ++j) {
			result[i+j][i] = vec[k++];
		}
		return;
	}

	for (int j = 0; j < c; ++j) {
		result[i][i + j] = vec[k++];
	}

	for (int j = 1; j < r; ++j) {
		result[i + j][i + c - 1] = vec[k++];
	}

	for (int j = c - 2; j >= 0; --j) {
		result[i + r - 1][j + i] = vec[k++];
	}

	for (int j = r - 2;  j > 0; --j) {
		result[i + j][i] = vec[k++];
	}

	gao(vec, k, result, i + 1, r - 2, c - 2);
}

void print(const vector<vector<int>> data, int r, int c) {
	for (int i = 0; i < r; ++i) {
		for (int j = 0; j < c; ++j) {
			if (0 == j) {
				printf("%d", data[i][j]);
			} else {
				printf(" %d", data[i][j]);
			}

			if (j == c - 1) {
				printf("\n");
			}
		}
	}
}

int main() {
	vector<int> numbers;
	int n;
	scanf("%d", &n);
	numbers.resize(n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &numbers[i]);
	}

	std::sort(numbers.begin(), numbers.end(), 
			std::greater<int>());

	pair<int, int> rc = getRowColumn(n);

	vector<vector<int>> result;
	result.resize(rc.first);
	for (int i = 0; i < rc.first; ++i)
		result[i].resize(rc.second);

	gao(numbers, 0, result, 0, rc.first, rc.second);
	print(result, rc.first, rc.second);
	return 0;
}

I wrote a post of solving a similar spiral matrix problem before: Spiral Matrix I and II: Recursive and Iterative Index Calculation.

Be careful about the cases where the resulted matrix has only 1 column or row, and the cases where the number of rows equal to the number of columns, make sure the caclulation of the rows and columns are correct, test with n = 0, 1, 2, 3, 4.

Summary

I have given recurisve algorithm, test cases, and related problem references in this post to solve PAT Advanced 1105 Spiral Matrix.

Written on June 19, 2016