PAT(B) 1050 螺旋矩陣（Java：24分）

題目連結：1050 螺旋矩陣 (25 point(s))

題目描述

本題要求将給定的 N 個正整數按非遞增的順序，填入“螺旋矩陣”。所謂“螺旋矩陣”，是指從左上角第 1 個格子開始，按順時針螺旋方向填充。要求矩陣的規模為 m 行 n 列，滿足條件：m×n 等于 N；m≥n；且 m−n 取所有可能值中的最小值。

輸入格式

輸入在第 1 行中給出一個正整數 N，第 2 行給出 N 個待填充的正整數。所有數字不超過 10​4​​，相鄰數字以空格分隔。

輸出格式

輸出螺旋矩陣。每行 n 個數字，共 m 行。相鄰數字以 1 個空格分隔，行末不得有多餘空格。

測試樣例

Case 0:

12
37 76 20 98 76 42 53 95 60 81 58 93
           

98 95 93
42 37 81
53 20 76
58 60 76
           

Case 1:

5
3 2 4 1 5
           

5
4
3
2
1
           

Java代碼

/**********************************************************************************
Submit Time			Status	Score	Problem	Compiler		Run Time	User
8/25/2019, 21:41:14	PA		24		1050	Java (openjdk)	177 ms		wowpH
Case 7: TLE
**********************************************************************************/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String[] arr = br.readLine().split(" ");
		int[] num = new int[N];
		for (int i = 0; i < N; ++i) {
			num[i] = Integer.parseInt(arr[i]);
		}
		Arrays.sort(num);									// 所有數字升序排序

		int n = (int) Math.sqrt(N);						// 開方得到 n 的可能最大值
		while (0 != N % n) {					// 餘數不為0，則 m 不是整數，不合要求
			--n;											// n 自減
		}
		int m = N / n;										// m × n = N

		int[][] matrix = new int[m][n];						// m × n 的矩陣
		int direction = 0;			// 方向，0代表向右，1代表向下，2代表向左，3代表向上
		int k1 = 0, k2 = 0;									// 矩陣下标
		for (int i = N - 1; i >= 0; --i) {					// 所有數
			matrix[k1][k2] = num[i];						// 指派給矩陣
			switch (direction) {							// 方向
			case 0:											// 向右
				if (k2 + 1 < n && 0 == matrix[k1][k2 + 1]) {// 右邊未越界且未指派
					++k2;									// 向右移動
				} else {									// 右邊越界或已經指派
					++k1;									// 向下移動
					direction = 1;							// 改變方向為向下
				}
				break;
			case 1:											// 向下
				if (k1 + 1 < m && 0 == matrix[k1 + 1][k2]) {// 下邊未越界且未指派
					++k1;									// 向下移動
				} else {									// 下邊越界或已經指派
					--k2;									// 向左移動
					direction = 2;							// 改變方向為向左
				}
				break;
			case 2:											// 向左
				if (k2 - 1 >= 0 && 0 == matrix[k1][k2 - 1]) {// 左邊未越界且未指派
					--k2;									// 向左移動
				} else {									// 左邊越界或已經指派
					--k1;									// 向上移動
					direction = 3;							// 改變方向為向上
				}
				break;
			default:										// 向上
				if (k1 - 1 >= 0 && 0 == matrix[k1 - 1][k2]) {// 上邊未越界且未指派
					--k1;									// 向上移動
				} else {									// 上邊越界或已經指派
					++k2;									// 向右移動
					direction = 0;							// 改變方向為向右
				}
			}
		}

		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n - 1; ++j) {
				System.out.print(matrix[i][j] + " ");		// 輸出矩陣
			}
			System.out.println(matrix[i][n - 1]);
		}
	}
}
           

送出結果