1010. 歪歪朋友圈

题目描述

在每一次旅游结束之后，歪歪都想把她的照片发到朋友圈上留下美好的回忆。但是其中朋友圈照片“九宫格”的排版往往让歪歪思考许久，经常反复拖动一张照片多次排版，以达到她内心的理想效果。朋友圈的照片拖动排版规则如下：将照片墙看作一个 n × m 的二维矩阵 A = [ai,j ]，其中 ai,j 表示第 i

行第 j 列位置上的照片编号。设一次拖动把位置 u = (x1, y1 ) 的照片移动到不同的位置 v = (x2, y2 )

。其中若满足：(x1 < x2 ) 或者 (x1 = x2 且 y1 < y2 )，我们称 u 在 v 的

“前面”。反之 u 在 v 的 “后面”。记变换后的矩阵为 B = [bi,j ]。

1. 若 u 在 v 的 “前面”，从 u 到 v 的经过位置按从上至下、从左至右的顺序依次为 p1, p2, ..., pk，其中 p1 = u，pk = v，则变换满足：

bpt = apt+1，1 ≤ t ≤ k − 1

bpk = ap1，并且其余位置保持不变。

可以把这个过程理解为：起点照片被取走，路径上的其他照片依次向前补位，最后把起点照片放到终点位置。

2. 若 u 在 v 的 “后面”，从 u 到 v 的经过位置按从下至上、从右至左的顺序依次为 p1, p2, ..., pk，其中 p1 = u，pk = v，则变换满足：

bpt = apt+1，1 ≤ t ≤ k − 1

bpk = ap1，并且其余位置保持不变。

可以把这个过程理解为：起点照片被取走，路径上的其他照片依次向后补位，最后把起点照片放到终点位置。例如，在一个 3 × 3 矩阵中，若把左上角的照片拖到中心位置，则矩阵变化可以写成：变换前

A 变换后 B

123

234

456

516

789

789

歪歪在排版朋友圈的时候会将照片一次性全部导入，然后再进行排版成她的理想状态。歪歪想知道对于她初始导入的 n × m 的朋友圈照片墙，最少要拖动几张照片才能达到她的理想状态呢？

输入格式

第一行输入测试用例组数 T。对于每组数据，第一行输入两个整数 n, m，表示输入照片墙的大小。接下来分别输入两个矩阵 A, B，其中矩阵 A 为歪歪初始输入的照片墙，矩阵 B 表示歪歪想排版成的照片墙。对于 A 矩阵会输入 n × m 个不同整数 ai,j，表示初始输入照片的编

号。对于 B 矩阵会输入 n × m 个不同整数 bi,j，表示想要排版成照片的

编号。数据保证：T ≤ 10，1 ≤ n × m ≤ 105，1 ≤ ai.j, bi,j ≤ 109，保证数

字集合 {ai,j } 与 {bi,j } 相同。

输出格式

对于每组数据输出歪歪最少需要拖动照片的数量。

样例输入

2
3 3
1 2 3
4 5 6
7 8 9
2 4 3
9 1 5
8 7 6
2 4
3 5 1 2
8 9 4 6
1 4 5 8
9 2 3 6

样例输出

5
4

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第10场）