This is a classic FloodFill question.
The idea is to choose a location first, and traverse through adjacent locations with the same height. If that height is the peak, there cannot be any higher location adjacent to the traversed locations. The idea can be considered as traversing the contour line of the given location in a contour map. The process is executed for all unvisited locations to detect all the peaks.
The algorithm visits each location once and checks all adjacent cells hence requires O(N*M) running time. Since it uses only two NxM matrices, and a queue with maximum size of N*M, it requires O(N*M) memory.
#include <fstream> #include <queue> using namespace std; #define MAX 1000 // 8 directions of the adjacent cells const int dir[8][2]={{-1,-1},{-1,0},{-1,1},{1,-1},{1,0},{1,1},{0,-1},{0,1}}; int N,M,mat[MAX][MAX],cnt; bool mark[MAX][MAX]; // marker matrix for floodfill queue<int> que; // floodfill queue // read input void readFile(char *inpFile) { ifstream f; f.open(inpFile); f >> N >> M; for (int i=0; i<N; i++) for (int j=0; j<M; j++) f >> mat[i][j]; f.close(); } // write peak counts void writeFile(char *outFile) { ofstream f; f.open(outFile); f << cnt << "\n"; f.close(); } // floodfill algorithm void floodfill(int y,int x) { // add first location to the queue que.push(y); que.push(x); bool peak=true; // floodfill loop for the connected locations // that have the same height with the current location do { // get the next location in the queue y=que.front(); que.pop(); x=que.front(); que.pop(); // check all adjacent locations for (int i=0; i<8; i++) { int newY=y+dir[i][0],newX=x+dir[i][1]; if (newY>=0 && newX>=0 && newY<n && newX<m) // if an adjacent location is higher // the current location is not a peak if (mat[y][x]<mat[newY][newX]) peak=false; // if an adjacent location has the same height // add it into the queue to visit else if (mat[y][x]==mat[newY][newX] && !mark[newY][newX]) { mark[newY][newX]=true; // mark the locations in the queue que.push(newY); que.push(newX); } } } while (!que.empty()); if (peak) cnt++; // if the current height is peak, increment the peak counter } int main() { readFile("guard.in"); for (int i=0; i<N; i++) for (int j=0; j<M; j++) // visit any land that is not visited if (mat[i][j]>0 && !mark[i][j]) floodfill(i,j); writeFile("guard.out"); }