[URI Online Judge] – 1599 – Peaks of Atlas

Morocco is cut by the Atlas Mountains, whose highest peak is Toubkal, with 4165 meters. These mountains give rise to many stories and myths throughout antiquity, as, for example, the 12 tasks of Hercules. Near the city of Marrakech is what is called “high Atlas”, the highest part of these mountains.

The study of the altitudes of the various peaks has been done for centuries. Ancient Berbers documents document the recording of different altitudes of the various points of the Atlas Mountains since the sixteenth century. The document is a map of the region divided into quadrants. In each quadrant is noted that the average height point. We know that a point is a peak if the height is greater than that quadrant of its neighbors (one quadrant has up to 8).

Your task in this exercise is to read this map and identify the peaks in the documented region.

Input

The entry consists of several instances and ends with the end of file (EOF).

Each instance corresponds to a region of the map and represented by a matrix N x M (1 ≤ N ≤ 1.000). The first row in each instance contains the integers N and M. For i = 1, 2,. . . N, (i + 1)-th row corresponte thei-th row of the matrix and contains M integers separated by a space.

Output

For each instance print the coordinates of the peaks of the corresponding map, one per line, sorted first by rows and, in case of tie, by columns. If there are no peaks, print -1. Print a blank line at the end ofeach instance.

Sample Input Sample Output
3 3
2 1 1
1 1 6
4 1 0
3 3
1 1 1
1 3 1
1 1 3
1 1
2 3
3 1

-1

#include <iostream>
using namespace std;
int main(){
 int n, m, i, j;
 bool has_peak, has_any_peak;
while (cin >> n >> m){
 int map[n][m];
has_any_peak = false;
for (i = 0; i < n; i++){
 for (j = 0; j < m; j++){
 cin >> map[i][j];
 }
 }
for (i = 0; i < n; i++){
 for (j = 0; j < m; j++){
 has_peak = true;
if (i - 1 >= 0 && map[i][j] <= map[i - 1][j])
 has_peak = false;
 if (j - 1 >= 0 && map[i][j] <= map[i][j - 1])
 has_peak = false;
 if (i - 1 >= 0 && j - 1 >= 0 && map[i][j] <= map[i - 1][j - 1])
 has_peak = false;
if (i + 1 < n && map[i][j] <= map[i + 1][j])
 has_peak = false;
 if (j + 1 < m && map[i][j] <= map[i][j + 1])
 has_peak = false;
 if (i + 1 < n && j + 1 < m && map[i][j] <= map[i + 1][j + 1])
 has_peak = false;
if (i + 1 < n && j - 1 >= 0 && map[i][j] <= map[i + 1][j - 1])
 has_peak = false;
 if (i - 1 >= 0 && j + 1 < m && map[i][j] <= map[i - 1][j + 1])
 has_peak = false;
if (has_peak){
 has_any_peak = true;
 cout << i + 1 << " " << j + 1 << endl;
 }
 }
 }
if (!has_any_peak) cout << -1 << endl;
cout << endl;
 }
 return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s