#P17642. [ICPC 2019 Yinchuan R] Largest Common Submatrix
[ICPC 2019 Yinchuan R] Largest Common Submatrix
题目描述
给定两个 的矩阵,每个矩阵中的元素均为 到 之间的整数且两两不同。你需要找出这两个矩阵之间最大的公共子矩阵。
例子:
矩阵 :
$$\begin{array}{ccc} 1 & 2 & 3\\ 4 & 5 & 6\\ 8 & 7 & 9\\ \end{array}$$矩阵 :
$$\begin{array}{ccc} 5 & 6 & 1\\ 7 & 9 & 3\\ 2 & 4 & 8\\ \end{array}$$最大公共子矩阵:
输入格式
第一行输入包含两个整数 和 ,表示每个矩阵的行数和列数。
接下来的 行,每行包含 个整数,表示第一个矩阵 。再接下来的 行,每行包含 个整数,表示第二个矩阵 。
保证 ,且对于任意两对不同的下标 和 ,总有 以及 。
输出格式
输出一个整数,表示最大公共子矩阵的大小。
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
4
提示
样例测试中的最大公共子矩阵:
$$\displaystyle \begin{array}{cc} 5 & 6\\ 1 & 2\\ \end{array}$$翻译由 DeepSeek V4 Pro 完成