Corner Detection in Grayscale Images

In this problem, you are given a grayscale image represented by an n x m matrix of integers, where each integer represents the intensity of a pixel. Your task is to detect corner points in the image. A pixel is considered a corner if it is not on the border of the image and the absolute difference between its value and each of its four immediate neighbors (up, down, left, right) is at least a given threshold T.

More formally, for a pixel located at position \((i,j)\) with intensity \(A_{i,j}\) (where \(2 \le i \le n-1\) and \(2 \le j \le m-1\)), it is considered a corner if the following conditions hold:

[ |A_{i,j} - A_{i-1,j}| \ge T, \quad |A_{i,j} - A_{i+1,j}| \ge T, \quad |A_{i,j} - A_{i,j-1}| \ge T, \quad |A_{i,j} - A_{i,j+1}| \ge T ]

Due to factors such as pixel discretization, noise, and distortion, the mathematically detected points might not perfectly coincide with human intuitive corners, yet they generally provide significant local features used in many applications.

You are free to choose any appropriate algorithm that adheres to the above definition to efficiently count the number of corner points.

inputFormat

The first line of input contains three integers n, m and T (the number of rows, number of columns, and the threshold, respectively). Each of the following n lines contains m integers representing the pixel intensities of the image.

Constraints:

• 3 \(\le n, m \le 1000\) (since we only consider non-border pixels)
• 0 \(\le A_{i,j} \le 10^9\)
• 0 \(\le T \le 10^9\)

outputFormat

Output a single integer, the number of corner points detected in the image.

sample

3 3 5
1 10 1
10 2 10
1 10 1

1