Median Filter

Interview

Time limit2sMemory limit128 MB

Summary
Apply a 3x3 median filter over an image and count filtered pixels whose median value is at least a given threshold.
Level

Easy3 of 10

Topics
Matrix, Sorting, Simulation
Solved
No attempts yet

Problem

When nine numbers are sorted, the median is the fifth number.

Image I is a two-dimensional array of pixels with size R × C. Each pixel stores a darkness value V, where 0 ≤ V ≤ 255. Both R and C are between 3 and 40, inclusive.

A 3 × 3 median filter slides over the image starting at the upper-left corner, moving right, then continuing from the next row. At each position, the nine covered pixel values are sorted and the median becomes one pixel of the filtered image J. Therefore, J has size (R - 2) × (C - 2).

Given image I and a threshold T, count how many pixels in J have value greater than or equal to T.

Input

The first line contains R and C. Each of the next R lines contains C pixel values for one row of the image. The last line contains the threshold T.

Output

Print the number of pixels in the filtered image J whose value is greater than or equal to T.

Examples1

  1. Example 1

    Input
    6 5
49 36 73 62 21
27 88 14 11 12
99 18 36 91 21
45 96 72 12 10
12 48 49 75 56
12 15 48 86 78
40
    Expected output
    7