#C14065. Finding Peaks in a 2D Grid

    ID: 43673 Type: Default 1000ms 256MiB

Finding Peaks in a 2D Grid

Finding Peaks in a 2D Grid

You are given a two-dimensional grid of integers with m rows and n columns. Your task is to identify all the peaks in the grid. A cell \(a_{ij}\) is considered a peak if it is strictly greater than each of its four neighbors: above, below, left, and right. Note that if a neighbor does not exist (i.e. the cell is on the boundary), it is ignored in the comparison.

In addition to identifying the peaks, you must compute two values:

  • The sum of the values of all peak cells.
  • The product of the values of all peak cells.

If no peaks are found, the sum should be reported as 0 and the product as 1.

Example 1:

Input:
3 4
1 4 3 2
3 5 6 4
2 2 1 3

Output: 1 2 6 6

</p>

Explanation: The only peak is at cell (1,2) (using 0-based indexing) whose value is 6.

Example 2:

Input:
3 3
10 12 14
9 15 13
8 11 12

Output: 0 2 1 1 29 210

</p>

Here, the peaks are at positions (0,2) and (1,1) with values 14 and 15 respectively.

inputFormat

The first line of input contains two space-separated integers m and n, representing the number of rows and columns respectively.

The next m lines each contain n space-separated integers, representing the grid.

Sample Input:

3 4
1 4 3 2
3 5 6 4
2 2 1 3

outputFormat

The output consists of three lines:

  • First line: If one or more peaks are identified, output their coordinates in the order encountered, with each coordinate represented as two integers (row and column) separated by a space. All coordinates should be printed on the same line separated by a single space. If no peak exists, output None.
  • Second line: The sum of the values at the peak positions.
  • Third line: The product of the values at the peak positions.

All the indices are 0-based.

Sample Output:

1 2
6
6
## sample
3 4
1 4 3 2
3 5 6 4
2 2 1 3
1 2

6 6

</p>