小杨的鞍点

• 时间限制：1.0 s
• 内存限制：512.0 MB

题目描述

小杨有一个 $n$ 行 $m$ 列的整数矩阵。他把矩阵中满足以下条件的位置称为"鞍点"：

• 该位置上的数，是它所在行的最大值；
• 同时，该位置上的数，是它所在列的最小值。

请你帮小杨找出矩阵中所有鞍点的个数，并按行号从小到大、行号相同时按列号从小到大的顺序，输出每个鞍点的坐标（行号、列号均从 $1$ 开始编号）。

注意：一行的最大值可能出现在多个位置，一列的最小值也可能出现在多个位置，只要某个位置上的数同时等于"所在行的最大值"和"所在列的最小值"，它就是鞍点。

输入格式

第一行两个整数 $n, m$，表示矩阵的行数和列数。

接下来 $n$ 行，每行 $m$ 个整数 $a_{i,j}$，用空格隔开，表示整个矩阵。

输出格式

第一行一个整数 $k$，表示鞍点的个数。

接下来 $k$ 行，每行两个整数，表示一个鞍点的行号和列号（从 $1$ 开始编号），按行号从小到大、列号从小到大输出。

输入输出样例

输入样例 #1

3 3
1 2 3
4 5 6
7 8 9

输出样例 #1

1
1 3

输入样例 #2

2 2
5 5
5 5

输出样例 #2

4
1 1
1 2
2 1
2 2

样例 1 解释

• 第 1 行的最大值是 $3$，位于 $(1, 3)$；
• 第 3 列的最小值是 $3$，位于 $(1, 3)$；
• 所以 $(1, 3)$ 是鞍点，其余位置都不满足条件。

数据范围

• $1 \le n, m \le 100$
• $-10000 \le a_{i,j} \le 10000$

提示

这是一道典型的"二维数组预处理 + 枚举"题目：

1. 先开两个数组 rowMax[i] 和 colMin[j]；
2. 两层循环求出每一行的最大值、每一列的最小值；
3. 再枚举矩阵中的每一个位置，判断它是否同时等于 rowMax[i] 和 colMin[j]；
4. 按行优先顺序枚举，天然就满足题目要求的输出顺序。