2023-11-18：用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-18：

go，c++，c的代码用灵捷3.5编写，go和c++有修改。

具体步骤如下：

1.通过输入获取大矩阵的大小n和m。

2.将输入的数据按行列填充到数组arr中。

3.根据行遍历，对每一行调用manacher函数进行回文串的预处理。该函数会在rp数组中保存每个位置向右的回文长度。

4.根据列遍历，对每一列调用manacher函数进行回文串的预处理。该函数会在cp数组中保存每个位置向下的回文长度。

5.遍历所有内部的行和列，计算每个位置上、下、左、右四个方向上的回文长度，并取其最小值作为当前位置的enlarge值。

6.统计enlarge数组中每个奇数行、奇数列位置的值除以2的结果，作为神奇矩阵的数量。

7.统计enlarge数组中每个偶数行、偶数列位置的值减去1后除以2的结果，再累加到神奇矩阵的数量。

8.返回神奇矩阵的数量作为结果。

总的时间复杂度：O(n * m * log(min(n, m)))，其中n为矩阵的行数，m为矩阵的列数。主要耗时的是manacher函数的预处理过程，而manacher函数的时间复杂度为O(log(min(n, m)))。

总的额外空间复杂度：O(n * m)，需要额外的数组保存回文长度。

go完整代码如下：

package main

import (
    "fmt"
)

const MAXN = 1001

var log2 [(MAXN<<1 | 1) + 1]int

var arr [MAXN<<1 | 1][MAXN<<1 | 1]int
var rp [MAXN<<1 | 1][MAXN<<1 | 1]int
var cp [MAXN<<1 | 1][MAXN<<1 | 1]int
var enlarge [MAXN<<1 | 1][MAXN<<1 | 1]int
var rmq [MAXN<<1 | 1][MAXN<<1 | 1]int
var s [MAXN<<1 | 1]int
var p [MAXN<<1 | 1]int
var n, m int

func init() {
    for k, j := 0, 1; j <= (MAXN<<1 | 1); j++ {
        if 1<<(k+1) <= j {
            k++
        }
        log2[j] = k
    }
}

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, r := 0, 1; i < n; i, r = i+1, r+2 {
        for j, c := 0, 1; j < m; j, c = j+1, c+2 {
            arr[r][c] = inputs[ii]
            ii++
        }
    }
    n = n*2 + 1
    m = m*2 + 1
    fmt.Println(number())

}

func number() int {
    for row := 0; row < n; row++ {
        manacher(row, 0, 0, 1)
    }
    for col := 0; col < m; col++ {
        manacher(0, col, 1, 0)
    }
    for row := 1; row < n-1; row++ {
        rowRmq(row)
        for col := 1; col < m-1; col++ {
            l := 1
            r := min(min(row+1, n-row), min(col+1, m-col))
            find := 1
            for l <= r {
                m := (l + r) / 2
                if query(col-m+1, col+m-1) >= m {
                    find = m
                    l = m + 1
                } else {
                    r = m - 1
                }
            }
            enlarge[row][col] = find
        }
    }
    for col := 1; col < m-1; col++ {
        colRmq(col)
        for row := 1; row < n-1; row++ {
            l := 1
            r := min(min(row+1, n-row), min(col+1, m-col))
            find := 1
            for l <= r {
                m := (l + r) / 2
                if query(row-m+1, row+m-1) >= m {
                    find = m
                    l = m + 1
                } else {
                    r = m - 1
                }
            }
            enlarge[row][col] = min(enlarge[row][col], find)
        }
    }
    ans := 0
    for row := 1; row < n-1; row += 2 {
        for col := 1; col < m-1; col += 2 {
            ans += enlarge[row][col] / 2
        }
    }
    for row := 2; row < n-1; row += 2 {
        for col := 2; col < m-1; col += 2 {
            ans += (enlarge[row][col] - 1) / 2
        }
    }
    return ans
}

func manacher(row int, col int, radd int, cadd int) {
    limit := 0
    for r, c := row, col; r < n && c < m; r, c = r+radd, c+cadd {
        s[limit] = arr[r][c]
        limit++
    }
    C := -1
    R := -1
    for i := 0; i < limit; i++ {
        p[i] = R
        if i < R {
            p[i] = min(p[2*C-i], R-i)
        } else {
            p[i] = 1
        }
        for i+p[i] < limit && i-p[i] > -1 && s[i+p[i]] == s[i-p[i]] {
            p[i]++
        }
        if i+p[i] > R {
            R = i + p[i]
            C = i
        }
    }
    var fill *[2003][2003]int
    if cadd == 1 {
        fill = &rp
    } else {
        fill = &cp
    }
    for i, r, c := 0, row, col; i < limit; i++ {
        fill[r][c] = p[i]
        r += radd
        c += cadd
    }
}

func rowRmq(row int) {
    for i := 0; i < m; i++ {
        rmq[i][0] = cp[row][i]
    }
    for j := 1; (1 << j) <= m; j++ {
        for i := 0; i+(1<<j)-1 < m; i++ {
            rmq[i][j] = min(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1])
        }
    }
}

func colRmq(col int) {
    for i := 0; i < n; i++ {
        rmq[i][0] = rp[i][col]
    }
    for j := 1; (1 << j) <= n; j++ {
        for i := 0; i+(1<<j)-1 < n; i++ {
            rmq[i][j] = min(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1])
        }
    }
}

func query(l int, r int) int {
    k := log2[r-l+1]
    return min(rmq[l][k], rmq[r-(1<<k)+1][k])
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

c++完整代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1001;

int log22[(MAXN << 1 | 1) + 1];
int arr[MAXN << 1 | 1][MAXN << 1 | 1];
int rp[MAXN << 1 | 1][MAXN << 1 | 1];
int cp[MAXN << 1 | 1][MAXN << 1 | 1];
int enlarge[MAXN << 1 | 1][MAXN << 1 | 1];
int rmq[MAXN << 1 | 1][MAXN << 1 | 1];
int s[MAXN << 1 | 1];
int p[MAXN << 1 | 1];
int n, m;

void manacher(int row, int col, int radd, int cadd);

int number();

void rowRmq(int row);

void colRmq(int col);

int query(int l, int r);

int min(int a, int b);

void init() {
    for (int k = 0, j = 1; j <= (MAXN << 1 | 1); j++) {
        if (1 << (k + 1) <= j) {
            k++;
        }
        log22[j] = k;
    }
}

int number() {
    for (int row = 0; row < n; row++) {
        manacher(row, 0, 0, 1);
    }
    for (int col = 0; col < m; col++) {
        manacher(0, col, 1, 0);
    }
    for (int row = 1; row < n - 1; row++) {
        rowRmq(row);
        for (int col = 1; col < m - 1; col++) {
            int l = 1;
            int r = min(min(row + 1, n - row), min(col + 1, m - col));
            int find = 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (query(col - mid + 1, col + mid - 1) >= mid) {
                    find = mid;
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }
            enlarge[row][col] = find;
        }
    }
    for (int col = 1; col < m - 1; col++) {
        colRmq(col);
        for (int row = 1; row < n - 1; row++) {
            int l = 1;
            int r = min(min(row + 1, n - row), min(col + 1, m - col));
            int find = 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (query(row - mid + 1, row + mid - 1) >= mid) {
                    find = mid;
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }
            enlarge[row][col] = min(enlarge[row][col], find);
        }
    }
    int ans = 0;
    for (int row = 1; row < n - 1; row += 2) {
        for (int col = 1; col < m - 1; col += 2) {
            ans += enlarge[row][col] / 2;
        }
    }
    for (int row = 2; row < n - 1; row += 2) {
        for (int col = 2; col < m - 1; col += 2) {
            ans += (enlarge[row][col] - 1) / 2;
        }
    }
    return ans;
}

void manacher(int row, int col, int radd, int cadd) {
    int limit = 0;
    for (int r = row, c = col; r < n && c < m; r += radd, c += cadd) {
        s[limit] = arr[r][c];
        limit++;
    }
    int C = -1;
    int R = -1;
    for (int i = 0; i < limit; i++) {
        p[i] = R;
        if (i < R) {
            p[i] = min(p[2 * C - i], R - i);
        }
        else {
            p[i] = 1;
        }
        while (i + p[i] < limit && i - p[i] > -1 && s[i + p[i]] == s[i - p[i]]) {
            p[i]++;
        }
        if (i + p[i] > R) {
            R = i + p[i];
            C = i;
        }
    }
    int(*fill)[2003];
    if (cadd == 1) {
        fill = rp;
    }
    else {
        fill = cp;
    }
    for (int i = 0, r = row, c = col; i < limit; i++) {
        fill[r][c] = p[i];
        r += radd;
        c += cadd;
    }
}

void rowRmq(int row) {
    for (int i = 0; i < m; i++) {
        rmq[i][0] = cp[row][i];
    }
    for (int j = 1; (1 << j) <= m; j++) {
        for (int i = 0; i + (1 << j) - 1 < m; i++) {
            rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
}

void colRmq(int col) {
    for (int i = 0; i < n; i++) {
        rmq[i][0] = rp[i][col];
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << j) - 1 < n; i++) {
            rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int l, int r) {
    int k = log22[r - l + 1];
    return min(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}

int min(int a, int b) {
    if (a < b) {
        return a;
    }
    return b;
}

int main() {
    init();
    int inputs[] = { 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 };
    int ii = 0;
    n = inputs[ii++];
    m = inputs[ii++];
    for (int i = 0, r = 1; i < n; i++, r += 2) {
        for (int j = 0, c = 1; j < m; j++, c += 2) {
            arr[r][c] = inputs[ii++];
        }
    }
    n = n * 2 + 1;
    m = m * 2 + 1;
    cout << number() << endl;
    return 0;
}

c完整代码如下：

#include <stdio.h>

#define MAXN 1001

int log2Arr[(MAXN << 1 | 1) + 1];
int arr[MAXN << 1 | 1][MAXN << 1 | 1];
int rp[MAXN << 1 | 1][MAXN << 1 | 1];
int cp[MAXN << 1 | 1][MAXN << 1 | 1];
int enlarge[MAXN << 1 | 1][MAXN << 1 | 1];
int rmq[MAXN << 1 | 1][MAXN << 1 | 1];
int s[MAXN << 1 | 1];
int p[MAXN << 1 | 1];
int n, m;

void init() {
    int k = 0;
    for (int j = 1; j <= (MAXN << 1 | 1); j++) {
        if (1 << (k + 1) <= j) {
            k++;
        }
        log2Arr[j] = k;
    }
}

int min(int a, int b) {
    return (a < b) ? a : b;
}

void manacher(int row, int col, int radd, int cadd) {
    int limit = 0;
    for (int r = row, c = col; r < n && c < m; r += radd, c += cadd) {
        s[limit] = arr[r][c];
        limit++;
    }

    int C = -1;
    int R = -1;
    for (int i = 0; i < limit; i++) {
        p[i] = R;
        if (i < R) {
            p[i] = min(p[2 * C - i], R - i);
        }
        else {
            p[i] = 1;
        }

        while (i + p[i] < limit && i - p[i] > -1 && s[i + p[i]] == s[i - p[i]]) {
            p[i]++;
        }

        if (i + p[i] > R) {
            R = i + p[i];
            C = i;
        }
    }

    int(*fill)[2003];
    if (cadd == 1) {
        fill = rp;
    }
    else {
        fill = cp;
    }

    for (int i = 0, r = row, c = col; i < limit; i++) {
        fill[r][c] = p[i];
        r += radd;
        c += cadd;
    }
}

void rowRmq(int row) {
    for (int i = 0; i < m; i++) {
        rmq[i][0] = cp[row][i];
    }

    for (int j = 1; (1 << j) <= m; j++) {
        for (int i = 0; i + (1 << j) - 1 < m; i++) {
            rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
}

void colRmq(int col) {
    for (int i = 0; i < n; i++) {
        rmq[i][0] = rp[i][col];
    }

    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << j) - 1 < n; i++) {
            rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int l, int r) {
    int k = log2Arr[r - l + 1];
    return min(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}

int number() {
    for (int row = 0; row < n; row++) {
        manacher(row, 0, 0, 1);
    }

    for (int col = 0; col < m; col++) {
        manacher(0, col, 1, 0);
    }

    for (int row = 1; row < n - 1; row++) {
        rowRmq(row);
        for (int col = 1; col < m - 1; col++) {
            int l = 1;
            int r = min(min(row + 1, n - row), min(col + 1, m - col));
            int find = 1;

            while (l <= r) {
                int mid = (l + r) / 2;
                if (query(col - mid + 1, col + mid - 1) >= mid) {
                    find = mid;
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }

            enlarge[row][col] = find;
        }
    }

    for (int col = 1; col < m - 1; col++) {
        colRmq(col);
        for (int row = 1; row < n - 1; row++) {
            int l = 1;
            int r = min(min(row + 1, n - row), min(col + 1, m - col));
            int find = 1;

            while (l <= r) {
                int mid = (l + r) / 2;
                if (query(row - mid + 1, row + mid - 1) >= mid) {
                    find = mid;
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }

            enlarge[row][col] = min(enlarge[row][col], find);
        }
    }

    int ans = 0;

    for (int row = 1; row < n - 1; row += 2) {
        for (int col = 1; col < m - 1; col += 2) {
            ans += enlarge[row][col] / 2;
        }
    }

    for (int row = 2; row < n - 1; row += 2) {
        for (int col = 2; col < m - 1; col += 2) {
            ans += (enlarge[row][col] - 1) / 2;
        }
    }

    return ans;
}

int main() {
    init();

    int inputs[] = { 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 };
    int ii = 0;

    n = inputs[ii];
    ii++;
    m = inputs[ii];
    ii++;

    for (int i = 0, r = 1; i < n; i++, r += 2) {
        for (int j = 0, c = 1; j < m; j++, c += 2) {
            arr[r][c] = inputs[ii];
            ii++;
        }
    }

    n = n * 2 + 1;
    m = m * 2 + 1;
    printf("%d\n", number());

    return 0;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接