online advertising

Sunday, April 2, 2017

HackerRank - Cavity Map

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