2023-11-18：用 go 语言，如果一个正方形矩阵上下对称并且左右对称，对称的意思是互为镜像，那么称这个正方形矩阵叫做神奇矩阵。比如 : 1 5 5 1 6 3 3 6 6 3 3 6 1 5

作者：福大大架构师每日一题

2023-11-18
北京
本文字数：6752 字
阅读完需：约 22 分钟

2023-11-18：用 go 语言，如果一个正方形矩阵上下对称并且左右对称，对称的意思是互为镜像，

那么称这个正方形矩阵叫做神奇矩阵。

比如 :

1 5 5 1

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]intvar rp [MAXN<<1 | 1][MAXN<<1 | 1]intvar cp [MAXN<<1 | 1][MAXN<<1 | 1]intvar enlarge [MAXN<<1 | 1][MAXN<<1 | 1]intvar rmq [MAXN<<1 | 1][MAXN<<1 | 1]intvar s [MAXN<<1 | 1]intvar p [MAXN<<1 | 1]intvar 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;}