Palindromic Matrix

本文最后更新于：3 years ago

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output

Input
The first line contains one integer n (1≤n≤20).

The second line contains n2 integers a1,a2,…,an2 (1≤ai≤1000) — the numbers to put into a matrix of n rows and n columns.

Output
If it is possible to put all of the n2 numbers into a matrix of n rows and n columns so that each number is used exactly once, each cell contains exactly one number and the resulting matrix is palindromic, then print “YES”. Then print n lines with n space-separated numbers — the resulting matrix.

If it’s impossible to construct any matrix, then print “NO”.

You can print each letter in any case (upper or lower). For example, “YeS”, “no” and “yES” are all acceptable.

Examples
input

1
2
4
1 8 8 1 2 2 2 2 2 2 2 2 1 8 8 1

output

1
2
3
4
5
YES
1 2 2 1
8 2 2 8
8 2 2 8
1 2 2 1

input

1
2
3
1 1 1 1 1 3 3 3 3

output

1
2
3
4
YES
1 3 1
3 1 3
1 3 1

input

1
2
4
1 2 1 9 8 4 3 8 8 3 4 8 9 2 1 1

output

1
NO

input

1
2
1
10

output

1
2
YES
10

解题方法:
给每个输入的数计数,取n/2为每个1/4矩阵的长,如果n为奇数,则还要增加两条中间的数,每条长度也为n/2,
构造1/4矩阵然后通过翻转得到完整的矩阵,每次从数组里取数,1/4矩阵每个位置的数都要是4个(因为要翻转得到完整矩阵),因此每次取4个数,取到达到n/2个为止,奇数的话要继续取两条链,每条长度为n/2,且每个数至少有一个,然后剩下的最后一个数为中心
上述取数过程中出现任意一次取不到数,则表示无法构造矩阵,输出NO,退出即可

代码如下:

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
class Solution():
    def __init__(self):
        n = int(input())
        num = []
        mat = []
        res = []
        for i in range(0, 1001):
            num.append(0)
        m = input().split()
        for i in range(n * n):
            if num[int(m[i])] == 0:
                res.append(int(m[i]))
            num[int(m[i])] += 1
        len = int(n / 2)
        f = True
        for i in range(len):
            for j in range(len):
                f = False
                for k in res:
                    if num[k] >= 4:
                        num[k] -= 4;
                        mat.append(k)
                        f = True
                        break
                if not f:
                    print('No')
                    return
        if n & 1:
            colum = []
            row = []
            for i in range(len):
                f = False
                for k in res:
                    if num[k] >= 2:
                        num[k] -= 2
                        colum.append(k)
                        f = True
                        break
                if not f:
                    print('No')
                    return
            for i in range(len):
                f = False
                for k in res:
                    if num[k] >= 2:
                        num[k] -= 2
                        row.append(k)
                        f = True
                        break
                if not f:
                    print('No')
                    return
            center = -1
            for i in res:
                if num[i] == 1:
                    num[i] = 0
                    center = i
                    break
            if center == -1:
                print('No')
                return
            print('Yes')
            for i in range(len):
                for j in range(len * i, len * i + len):
                    print(mat[j], end=' ')
                k = len * i + len - 1
                print(colum[i], end=' ')
                for j in range(len):
                    print(mat[k], end='')
                    if j == len - 1:
                        print()
                    else:
                        print(end=' ')
                    k -= 1
            i = len - 1
            for j in row:
                print(j, end=' ')
            print(center, end='')
            for j in row:
                print(' ' + str(row[i]), end='')
                i -= 1
            print()
            l = len - 1
            for i in range(len):
                result=[]
                for j in range(len * len - (i + 1) * len, len * len - (i + 1) * len + len):
                    result.append(mat[j])
                    print(mat[j], end=' ')
                k = len-1
                print(colum[l], end=' ')
                l -= 1
                for j in range(len):
                    print(result[k],end='')
                    if j == len - 1:
                        print()
                    else:
                        print(end=' ')
                    k -= 1
        else:
            print('Yes')
            for i in range(len):
                for j in range(len * i, len * i + len):
                    print(mat[j], end=' ')
                k = len * i + len - 1
                for j in range(len):
                    print(mat[k], end='')
                    if j == len - 1:
                        print()
                    else:
                        print(end=' ')
                    k -= 1
            l = len - 1
            for i in range(len):
                for j in range(len*len - len * i - len, len*len - len * i):
                    print(mat[j], end=' ')
                k = len*len - len * i - 1
                for j in range(len):
                    print(mat[k], end='')
                    if j == len - 1:
                        print()
                    else:
                        print(end=' ')
                    k -= 1


if __name__ == '__main__':
    Solution()