马鞍点

题目描述

给定 N×N 个整数构成一个矩阵 A₁,₁,…,Aₙ,ₙ。

矩阵的马鞍点，指的是数组中满足以下两个条件的位置：

• 它在所在行中是最小值
• 它在所在列中是最大值

请统计并输出给定矩阵马鞍点的数量。

输入格式

• 第一行：单个整数表示 N
• 第二行到第 N+1 行：在其中的第 i 行，有 N 个整数表示 Aᵢ,₁,…,Aᵢ,ₙ

输出格式

单个整数，表示马鞍点的数量。

数据范围

• 30% 的数据，1 ≤ N ≤ 10
• 60% 的数据，1 ≤ N ≤ 300
• 100% 的数据，1 ≤ N ≤ 1000
• 0 ≤ Aᵢ,ⱼ ≤ 1000

样例输入 #1

3
1 2 3
3 1 2
2 3 1

样例输出 #1

0

样例输入 #2

2
1 1
1 1

样例输出 #2

4

本题涉及的知识点从属于 GESP 四级，难度等级：⭐⭐

测试点分布