We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Cavity Map
  5. Discussions

Cavity Map

Sort by

recency

|

851 Discussions

|

  • alban_tyrex
     + 0 comments

    Here is my c++ solution, you can watch the explanation here : https://youtu.be/BweZoGPs08M

    vector<string> cavityMap(vector<string> grid) {
    for(int i = 1; i < grid.size() - 1; i++){
        for(int j = 1; j < grid[i].size()-1; j++){
            if(grid[i][j] > grid[i][j-1] && grid[i][j] > grid[i][j+1])
                if(grid[i][j] > grid[i-1][j] && grid[i][j] > grid[i+1][j])
                grid[i][j] = 'X'; 
        }
    }
    return grid;
}

  • mr_waite
     + 0 comments

    A solution in C# that is more slightly more optimized than the rest I've seen here. Because of how a cavity is defined in this, there are two conditions where you can skip evaluating the four adjacent locations:

    1. If the element preceding the current one in this row was a cavity, this one cannot be. We can use this to skip the next position by incrementing our loop an additional time while replacing the character in the string.
    2. If the element at this position in the previous row was a cavity, this one cannot be. We can take advantage of the short-circuit evaluation of C# to reduce the number of comparison operations by placing the [i - 1] [j] check first, as that will always be false if the cell at that position was changed to 'X'. (Note: not all languages use short-circuit evaluation, so for some languages this will change nothing)

    Combined, these two changes can remove up to approximately 3.5 * ((N - 2) ^ 2) / 2 comparison operations from our execution time!

    public static List<string> cavityMap(List<string> grid)
    {
        for (int i = 1; i < grid.Count - 1; i++)
        {
            for (int j = 1; j < grid[i].Length - 1; j++)
            {
                if (grid[i].ElementAt(j) > grid[i - 1].ElementAt(j) &&
                    grid[i].ElementAt(j) > grid[i + 1].ElementAt(j) &&
                    grid[i].ElementAt(j) > grid[i].ElementAt(j - 1) &&
                    grid[i].ElementAt(j) > grid[i].ElementAt(j + 1))
                {
                    
                    grid[i] = grid[i].Substring(0, j) + "X" + grid[i].Substring(++j);
                }
            }
        }
        return grid;
    }

  • zaidnsour12
     + 0 comments

    Java clean solutaion

    public static List<Character> getAdjacent(List<String> grid, int i,int j){
    return Arrays.asList(grid.get(i+1).charAt(j), grid.get(i-1).charAt(j),
            grid.get(i).charAt(j+1), grid.get(i).charAt(j-1));
    }
    
    public static int getInt(char c){
        return c - '0';
        }
       
    public static List<String> cavityMap(List<String> grid) {
    int n = grid.size();
    List<String> new_grid = new ArrayList<>();
    
    for(int i = 0; i < n; i++){
        String line = "";
        for(int j = 0; j < n; j++){
            char c = grid.get(i).charAt(j);
            if(i == 0 || i == n-1 || j == 0 || j == n-1){
                line += c;
                continue;
                }
            boolean is_cavity = true;
            
            
            for(char adj: getAdjacent(grid, i, j)){
                if(getInt(adj) >= getInt(c))
                  is_cavity = false; 
                }
            if(is_cavity)
                c = 'X';
            
            line += c;
            
            }
        new_grid.add(line);
        }
    
    return new_grid;

    }

  • dhihanlaksanaaj1
     + 0 comments

    SWIFT

    func cavityMap(grid: [String]) -> [String] {
    // Write your code here
    if grid.first!.count < 3 { return grid }
    
    var gridUTF8: [[UInt8]] = grid.map{ [UInt8]($0.utf8) }
    
    let gridMaxIndex: Int = gridUTF8.count - 1
    let gridContentMaxIndex: Int = gridUTF8.first!.count - 1
    
    for index1 in 1 ... gridMaxIndex - 1 {
        for index2 in 1 ... gridContentMaxIndex - 1 {
            let currentGrid: UInt8 = gridUTF8[index1][index2]
            let isHValid: Bool = gridUTF8[index1][index2 - 1] < currentGrid && gridUTF8[index1][index2 + 1] < currentGrid
            let isVValid: Bool = gridUTF8[index1 - 1][index2] < currentGrid && gridUTF8[index1 + 1][index2] < currentGrid
            if isHValid && isVValid  {
                gridUTF8[index1][index2] = 88
                continue
            }
        }
    }
    
    return gridUTF8.map{ String(bytes: $0, encoding: String.Encoding.utf8) ?? "" }
}

  • cscys_2310807
     + 0 comments
    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
void cavityMap(int n,char** grid){
    for(int i=1;i<n-1;i++){
        for(int j=1;j<n-1;j++){
            if(grid[i][j]>grid[i][j-1]&&grid[i][j]>grid[i][j+1]&&grid[i][j]>grid[i-1][j]&&grid[i][j]>grid[i+1][j]){
                grid[i][j]='X';
            }
        }
    }
    for(int i=0;i<n;i++){
        printf("%s\n", grid[i]);
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    char** grid=(char**)malloc(n*sizeof(char*));
    for(int i=0;i<n;i++)
    {
        grid[i]=(char*)malloc((n+1)*sizeof(char));
        scanf("%s",grid[i]);
    }
    cavityMap(n,grid);
    for(int i=0;i<n;i++)
        free(grid[i]);
    free(grid);
    return 0;
}