#B. 希蒙的山

    传统题 1000ms 256MiB

希蒙的山

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

希蒙有着 nnmm 列的土地,第 ii 行第 jj 列的土地初始海拔为 ai,ja_{i,j}。行号和列号均从 11 开始编号。

在漫长的岁月中,一共发生了 TT 次地理变迁。每次地理变迁,两块土地的海拔会发生交换。

如果有一块土地,比上下左右直接相邻的土地海拔都高,我们称其为一个山峰。

希蒙想要知道,在所有地理变迁完成后,他一共有多少山峰,它们的坐标分别为多少。

例如:n=m=3n=m=3,海拔高度如下所示

1  2  31  4  21  1  21 \ \ 2 \ \ 3 \\ 1 \ \ 4 \ \ 2\\ 1 \ \ 1 \ \ 2

其中,(1,3),(2,2)(1,3),(2,2) 是山峰。

输入格式

输入的第一行为两个整数 n,mn,m,分别代表行数与列数。

接下来 nn 行,每行 mm 个整数,第 ii 行第 jj 个整数代表 ai,ja_{i,j}

接下来一行一个整数 TT

接下来 TT 行,每行四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,代表 x1x_1y1y_1 列的土地与 x2x_2y2y_2 列的土地发生了地理变迁。

输出格式

输出的第一行为一个整数,代表地理变迁后山峰的数量 kk

接下来 kk 行,每行两个整数 x,yx,y,代表一座山峰在第 xx 行第 yy 列。

按照从上到下,自左向右的顺序输出山峰的坐标。

样例 #1

样例输入 #1

3 3
1 2 3
1 4 2
1 1 2
0

样例输出 #1

2
1 3 
2 2

样例 #2

样例输入 #2

3 3
1 2 3
1 2 2
1 1 4
1
2 2 3 3

样例输出 #2

2
1 3
2 2

提示

对于 20%20\% 的数据,n=1n=1; 对于另外 20%20\% 的数据,m=1m=1; 对于另外 20%20\% 的数据,n=mn=m; 对于另外 20%20\% 的数据,T=0T=0; 对于 100%100\% 的数据, $1 \le n,m \le 1000, 0 \le T \le 10^5, 1 \le a_{i,j} \le 10^6, 1\le x_1,x_2\le n, 1\le y_1,y_2\le m$。

GESP讲师辅导能力考核-C++

未参加
状态
已结束
规则
IOI
题目
3
开始于
2024-2-22 13:00
结束于
2024-2-22 14:30
持续时间
1.5 小时
主持人
参赛人数
3