2023-11-15：用go语言，如果一个正方形矩阵上下对称并且左右对称，对称的意思是互为镜像，
那么称这个正方形矩阵叫做神奇矩阵，
比如 :
1 5 5 1
6 3 3 6
6 3 3 6
1 5 5 1
这个正方形矩阵就是神奇矩阵。
给定一个大矩阵n*m，返回其中神奇矩阵的数目。
1 <= n,m <= 1000。
来自左程云。
答案2023-11-15：
go代码用灵捷3.5编写。
大体过程如下：
1.定义常量MAXN为1001，定义常量baser为491，定义常量basec为499。
2.定义数组powr和powc，分别计算baser和basec的幂次，用于后续计算哈希值。
3.定义数组arr1、arr2、arr3，分别存储原数组、上下对称数组、左右对称数组。
4.定义数组sum1、sum2、sum3，分别存储三个数组的前缀哈希和。
5.通过循环读取输入的n、m和矩阵元素，并顺便把元素存入arr1、arr2、arr3对应位置。
6.构建arr1、arr2、arr3的前缀哈希和，存入sum1、sum2、sum3中。
7.定义函数hash，用于计算矩阵中(a,b)到(c,d)范围内的哈希值。
8.定义函数ok，用于判断以(a,b)到(c,d)范围内的正方形是否为神奇矩阵。
9.定义函数number，用于统计大矩阵中神奇矩阵的数量。分别计算奇数长度和偶数长度的正方形数量，返回总数量。
10.在主函数中调用上述各个函数，输出最终结果。
11.总时间复杂度为O(n^2 * logn)，总额外空间复杂度为O(n^2)。
go完整代码如下：
代码语言：javascript复制package main
import (
"fmt"
)
const MAXN int = 1001
const baser int = 491
const basec int = 499
var powr [MAXN]int64
var powc [MAXN]int64
var arr1 [MAXN][MAXN]int
var arr2 [MAXN][MAXN]int
var arr3 [MAXN][MAXN]int
var sum1 [MAXN][MAXN]int64
var sum2 [MAXN][MAXN]int64
var sum3 [MAXN][MAXN]int64
var n int
var m int
func init() {
powr[0] = 1
powc[0] = 1
for i := 1; i < MAXN; i {
powr[i] = powr[i-1] * int64(baser)
}
for i := 1; i < MAXN; i {
powc[i] = powc[i-1] * int64(basec)
}
}
func buildHash(arr *[MAXN][MAXN]int, sum *[MAXN][MAXN]int64) {
for i := 1; i <= n; i {
for j := 1; j <= m; j {
sum[i][j] = sum[i][j-1]*int64(basec) int64(arr[i][j])
}
}
for i := 1; i <= n; i {
for j := 1; j <= m; j {
sum[i][j] = sum[i-1][j] * int64(baser)
}
}
}
func hash(sum *[MAXN][MAXN]int64, a int, b int, c int, d int) int64 {
ans := sum[c][d] - sum[a-1][d]*powr[c-a 1] - sum[c][b-1]*powc[d-b 1] sum[a-1][b-1]*powr[d-b 1]*powc[c-a 1]
return ans
}
func number() int {
ans := 0
// 奇数长度，实点做中心
for i := 1; i <= n; i {
for j := 1; j <= m; j {
l := 1
r := min(min(i, n-i 1), min(j, m-j 1))
find := 1
var m int
for l <= r {
m = (l r) / 2
if ok(i-m 1, j-m 1, i m-1, j m-1) {
find = m
l = m 1
} else {
r = m - 1
}
}
ans = find
}
}
// 偶数长度
// 虚点做中心
for i := 1; i < n; i {
for j := 1; j < m; j {
// 左上角点为代表
l := 1
r := min(min(i, j), min(n-i, m-j))
find := 0
var m int
for l <= r {
m = (l r) / 2
if ok(i-m 1, j-m 1, i m, j m) {
find = m
l = m 1
} else {
r = m - 1
}
}
ans = find
}
}
return ans
}
func ok(a int, b int, c int, d int) bool {
if a == c {
return true
}
h1 := hash(&sum1, a, b, c, d)
h2 := hash(&sum2, n-c 1, b, n-a 1, d)
h3 := hash(&sum3, a, m-d 1, c, m-b 1)
return h1 == h2 && h1 == h3
}
func min(x int, y int) int {
if x < y {
return x
}
return y
}
func main() {
inputs := []int{5, 5,
4, 2, 4, 4, 4,
3, 1, 4, 4, 3,
3, 5, 3, 3, 3,
3, 1, 5, 3, 3,
4, 2, 1, 2, 4}
ii := 0
n = inputs[ii]
ii
m = inputs[ii]
ii
for i := 1; i <= n; i {
for j := 1; j <= m; j {
arr1[i][j] = inputs[ii]
ii
arr2[n-i 1][j] = arr1[i][j]
arr3[i][m-j 1] = arr1[i][j]
}
}
buildHash(&arr1, &sum1)
buildHash(&arr2, &sum2)
buildHash(&arr3, &sum3)
fmt.Println(number())
}
在这里插入图片描述
