Under construction

Still being built. Things may change

Farm Management

Interview

Time limit2sMemory limit128 MB

Summary
Count 8-directionally connected groups of equal-height cells in a grid where every outside neighbor is strictly lower.
Level

Medium5 of 10

Topics
BFS, DFS, Matrix, Implementation
Solved
No attempts yet

Problem

Minsik's farm is an N by M grid. To manage the farm, he wants to place one guard on each mountain peak. Your task is to count how many mountain peaks are in the farm.

A mountain peak is either one cell, or a connected group of adjacent cells, all with the same height. Two cells are adjacent when both the difference between their row numbers and the difference between their column numbers are at most 1. In other words, horizontal, vertical, and diagonal neighbors are all adjacent.

For such a group to be a mountain peak, every cell adjacent to the group but not included in it must have height strictly lower than the group's height. Cells outside the grid are not considered adjacent cells.

Given the farm grid, find the number of mountain peaks.

Input

The first line contains two integers N (1 < N ≤ 100) and M (1 < M ≤ 70).

Each of the next N lines contains M integers, where each integer is the height of a grid cell. Every height is a non-negative integer not greater than 500.

Output

Print the number of mountain peaks on the first line.

Examples1

  1. Example 1

    Input
    8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0
    Expected output
    3