[PAT-A] 1105 Spiral Matrix

Java

测试点6超时

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        int[] a = new int[n];

        String[] input = reader.readLine().trim().split(" ");
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(a);
        for (int i = 0; i < n / 2; i++) {
            int temp = a[i];
            a[i] = a[n - i - 1];
            a[n - i - 1] = temp;
        }

        int row = 0, col = 0;
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                row = n / i;
                col = i;
            }
        }

        int[][] g = new int[row][col];
        boolean[][] visited = new boolean[row][col];
        int[][] d = {
            {0, 1, 0, -1},
            {1, 0, -1, 0}
        };

        int cnt = 0, k = 0;
        int x = 0, y = 0;
        while (cnt < n) {
            g[x][y] = a[cnt++];
            visited[x][y] = true;

            int nx = x + d[0][k], ny = y + d[1][k];
            if (nx < 0 || nx >= row || ny < 0 || ny >= col || visited[nx][ny]) {
                k = (k + 1) % 4;
                nx = x + d[0][k];
                ny = y + d[1][k];
            }
            x = nx;
            y = ny;
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (j > 0) System.out.print(" ");
                System.out.print(g[i][j]);
            }
            System.out.println();
        }
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int n, row, col;    // row >= col
int a[N], g[N][N];
int d[][4] = {
        {0, 1, 0,  -1},
        {1, 0, -1, 0},
};

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

    sort(a, a + n, greater<int>());

    for (int i = 1; i <= n / i; ++i)
        if (n % i == 0) {
            row = n / i;
            col = i;
        }

    int cnt = 0, k = 0;
    int x = 0, y = 0;
    while (cnt < n) {
        g[x][y] = a[cnt++];

        int nx = x + d[0][k], ny = y + d[1][k];
        if (g[nx][ny] || nx < 0 || nx >= row || ny < 0 || ny >= col) {
            k = (k + 1) % 4;
            nx = x + d[0][k], ny = y + d[1][k];
        }
        x = nx;
        y = ny;
    }

    for (int i = 0; i < row; ++i) {
        for (int j = 0; j < col; ++j) {
            if (j > 0) printf(" ");
            printf("%d", g[i][j]);
        }
        printf("\n");
    }

    return 0;
}