#P0820. 拼图游戏

拼图游戏

题目描述

jikong 正在玩一款数字拼图游戏。游戏界面是一个 NN 行 MM 列的大拼图板(大矩阵),每个格子里有 0∼90\sim9 的数字。

现在他手里有一个 nn 行 mm 列的小拼图块(小矩阵),他想知道这个小拼图块是否有可能是从大拼图板上完整切下来的一部分(不能旋转翻转,必须是原样连续的矩形块),如果有可能是,有多少个不同的位置可能切出这个小拼图块。

例如大拼图板可以写成:$\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}$,其中 [1245] \begin{bmatrix} 1 & 2 \\ 4 & 5 \end{bmatrix} 是它的一个小拼图块,而 [1425] \begin{bmatrix} 1 & 4 \\ 2 & 5 \end{bmatrix} 不是它的小拼图块。

输入格式

第一行包含两个整数N,M(1≤N,M≤50)N, M(1 \le N, M \le 50),表示大拼图板的大小。

接下来NN行,每行包含MM个数字,表示这个拼图板的内容。

第N+2N + 2行包含两个整数n,m(1≤n,m≤50)n, m(1 \le n, m \le 50),表示小拼图块的大小。

接下来nn行,每行包含mm个数字,表示这个小拼图块的内容。

题目保证:n≤N,m≤Mn \le N, m \le M。

输出格式

第一行输出一个整数cntcnt,在大拼图板上能完整切下来和这个小拼图块一模一样的部分的数量。

接下来cntcnt行,每行输出两个整数rr和cc,表示一处大拼图板上和小拼图块一模一样部分的左上角的格子在大拼图板上的行和列的位置(大拼图板的行和列均从11开始)。输出顺序按照行优先(先行后列)从小到大输出。

样例

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