本文共 2407 字，大约阅读时间需要 8 分钟。

Largest Common Submatrix

You are given two n×m matrices, and the elements of each matrix are ranged from

1 to n×m and pairwise distinct. You need to find the common submatrix with the largest size between these two matrices. Example: Matrix A: 1 2 3 4 5 6 8 7 9 Matrix B: 5 6 1 7 9 3 2 4 8 Largest common submatrix: 5 6 7 9

Input

The first line of input contains two integers n (1≤n≤1000) and m(1≤m≤1000), denoting the number of rows and columns of each matrix.

Each of the next n lines contain m integers per line, denoting the first matrix A=(ai,j)_{n×m}. And again, each of the next n lines contains m integers per line, denoting the second matrix B=(bi,j)n×m.

It is guaranteed that 1≤ai,j,bi,j≤n×m, and ai1,j1≠ai2,j2∧bi1,j1≠bi2,j2 always holds or each pair of (i1,j1) and (i2,j2), where i1≠i2∨j1≠j2.

Output

Output an integer representing the size of the largest common submatrix.

Sample Input

3 4

5 6 7 8 1 2 3 4 9 10 11 12 5 6 8 7 1 2 4 3 12 11 10 9

Sample Output

4

Sample Explain

Largest common submatrix in the sample test:

5 6 1 2

题意

给两个矩阵，问最大的公共子矩阵的大小是多少。

题解

将一个原矩阵转换为顺序矩阵如

1 2 3 4 5 6 7 8 9 10 11 12 另一个矩阵转换为其的映射，然后悬线法解决。

#include 
   
    using namespace std;const int MAXN = 1005;int n, m;int a[MAXN][MAXN], b[MAXN * MAXN];int l[MAXN][MAXN], r[MAXN][MAXN], u[MAXN][MAXN];int ans;int main() {
       scanf("%d%d", &n, &m);    for (int i = 1, x; i <= n * m; i++) {
           scanf("%d", &x);        b[x] = i;    }    for (int i = 1; i <= n; i++) {
           for (int j = 1, x; j <= m; j++) {
               scanf("%d", &x);            a[i][j] = b[x];            l[i][j] = r[i][j] = j;            u[i][j] = 1;        }    }    for (int i = 1; i <= n; i++) {
           for (int j = 2; j <= m; j++) {
               if (a[i][j] == a[i][j - 1] + 1) {
                   l[i][j] = l[i][j - 1];            }        }        for (int j = m - 1; j; j--) {
               if (a[i][j] == a[i][j + 1] - 1) {
                   r[i][j] = r[i][j + 1];            }        }    }    for (int i = 1; i <= n; i++) {
           for (int j = 1; j <= m; j++) {
               if (i > 1 && a[i][j] == a[i - 1][j] + m) {
                   l[i][j] = max(l[i][j], l[i - 1][j]);                r[i][j] = min(r[i][j], r[i - 1][j]);                u[i][j] = u[i - 1][j] + 1;            }            int x = r[i][j] - l[i][j] + 1;            ans = max(ans, x * u[i][j]);        }    }    printf("%d\n", ans);    return 0;}
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/108827073 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！