**Problem:**

Please find the problem here.

**Solution:**

This is really just finding the local minimums, go through all of the candidates (the slots that is not on the edge) and check one by one would work.

**Analysis:**

I could potentially goes faster because for every pair of number I checked twice, but asymptotically, this is optimal.

**Code:**

#include "stdafx.h" // https://www.hackerrank.com/challenges/cavity-map #include "HACKER_RANK_CAVITY_MAP.h" #include <math.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <assert.h> #include <limits.h> #include <stdbool.h> using namespace std; int HACKER_RANK_CAVITY_MAP() { int i, j, n; scanf("%d", &n); char** grid = (char**)malloc(sizeof(char*) * n); for (int grid_i = 0; grid_i < n; grid_i++) { grid[grid_i] = (char *)malloc(10240 * sizeof(char)); scanf("%s", grid[grid_i]); } for (i = 1; i < n - 1; i++) { for (j = 1; j < n - 1; j++) { if (grid[i - 1][j] < grid[i][j] && grid[i + 1][j] < grid[i][j] && grid[i][j - 1] < grid[i][j] && grid[i][j + 1] < grid[i][j]) { grid[i][j] = 'X'; } } } for (int grid_i = 0; grid_i < n; grid_i++) { printf("%s\n", grid[grid_i]); } return 0; }

## No comments :

## Post a Comment