Why am I Getting incorrect answer for large inputs

Question

You are given a square n×n map. Each cell of the map has a value in it denoting the depth of the appropriate area. We will call a cell of the map a cavity if and only if this cell is not on the border of the map and each cell adjacent to it has strictly smaller depth. Two cells are adjacent if they have a common side.

You need to find all the cavities on the map and depict them with character X.

Input Format

The first line contains an integer n (1≤n≤100), denoting the size of the map. Each of the following n lines contains n positive digits without spaces. A digit (1-9) denotes the depth of the appropriate area.

Output Format

Output n lines, denoting the resulting map. Each cavity should be replaced with character X.

Sample Input

 4
 1112   
 1912 
 1892
 1234

Sample Output

 1112
 1X12
 18X2
 1234

Now, I made this code. But this shows incorrect answer for large values, that is the value of n being 99 or 100 or 96.

This basically takes the input number and divides each row of the input array into individual digits. Then it compares each digit with the next and previous digit to check if it is greater than or less than the considered digit. However, it shows wrong answer for large values of n.

Here is the working code. ( Works fine on sample input )

#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

int main(void) {
    int n, i = 0;
    cin >> n;
    int values[1000];
    int j;
    for (i = 0; i < n; i++) {
        int p;
        cin >> p;
        values[i] = p;
    }
    char digits[1000][1000];
    int foo;
    for (i = 0; i < n; i++) {
        foo = n - 1;
        while (values[i] != 0) {
            digits[i][foo] = values[i] % 10 + 48;
            values[i] = values[i] / 10;
            foo--;
        }
    }

    for (i = 1; i < n - 1; i++) {
        j = 1;
        while (j != n - 1) {
            if (digits[i][j] > digits[i][j - 1] &&
                digits[i][j] > digits[i][j + 1]) {
                digits[i][j] = 'X';
            }
            j++;
        }
    }

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%c", digits[i][j]);
        }
        printf("\n");
    }
    return 0;
}

This shows incorrect answer for large values of the input such as the value of n being 96 or 100. I don't understand why? Is there any way I can optimize it?

Test Input File Link

Not working for the above input.

PS: This is not a homework question. I am not able to guess how to solve it.

Answer 1

You are only checking two adjacent cells. Each cell has four adjacent cells: left, right, up down. You need to also check the top and bottom cells like this:

if ( digits[i][j] > digits[i][j-1] && digits[i][j] > digits[i][j+1] && digits[i][j] > digits[i-1][j] && digits[i][j] > digits[i+1][j] )
{
    digits[i][j] = 'X';
}

Answer 2

Some problems in the code:

• In the input content provided in the question the number are in a range represented by a int type variable, but the content of the numbers in the file reference by the link provided the numbers are way out of range of any integer type in C++. You need to be able to storage up to 100 digits. This is the primary cause of your problem, it's the digits of each row. You could treat then as std::string to solved.
• According to the description of the problem a check is needed to cell adjacent upper and down.

Some improvement:

• Using std::vector instead of C array. Don't need to waste unused memory (by the way in the statement of the problem they say the number of rows would be between 1 and 100, you could declared values and digits variables to that lenght), the vector manage their memory automatically (grow when needed), they have checking of out of bound indexing, etc...
• Using std::string instead of int, (read previous why).
• Using std::getline to read the file line by line.
• The values of the std::string could be compared as char because they are digits, and '0' = 0x30 .. '9' = 0x39 and the same order of the digit apply to their char representation.

Code (Tested GCC 4.9.0 with C++11):

#include <iostream>
#include <vector>

int main(int argc, char* argv[]) {
    unsigned int lines;
    std::cin >> lines;

    std::vector<std::string> values;
    values.reserve(lines);

    // Reading the matrix
    std::string line;
    std::getline(std::cin, line); // Reading the rest of the first line
    while (std::getline(std::cin, line)) {
        values.push_back(line);
    }

    // Checking the depths and marking the cavities
    for (unsigned int i = 1; i < values.size() - 1; i++) {
        const auto& actual_number = values[i];
        for (unsigned int j = 1; j < actual_number.size() - 1; j++) {
            if (actual_number[j] > actual_number[j - 1] &&
                actual_number[j] > actual_number[j + 1] &&
                actual_number[j] > values[i - 1][j] &&
                actual_number[j] > values[i + 1][j]) {
                values[i][j] = 'X';
            }
        }
    }

    // Printing output
    for (const auto& n : values) {
        std::cout << n << std::endl;
    }
    return 0;
}

With the big sample input file, the output is the same numbers because they are all 9, there is no one bigger.

A version using as base the provided code:

#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;
int main(void) {
    int n, i = 0;
    cin >> n;
    char values[100][100]; // changed the limit
    int j;
    for (i = 0; i < n; i++) {
        cin >> values[i]; // reading the line. 'int p;' not necessary
    }

    // declaration of digits, and initialization not necessary

    for (i = 1; i < n - 1; i++) {
        j = 1;
        while (j != n - 1) {
            if (values[i][j] > values[i][j - 1] &&
                values[i][j] > values[i][j + 1] &&
                values[i][j] > values[i - 1][j] &&
                values[i][j] > values[i + 1][j]) {
                values[i][j] = 'X';
            }
            j++;
        }
    }

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%c", values[i][j]);
        }
        printf("\n");
    }
    return 0;
}

Answer 3

It is a bad idea to define two arrays one of which has elements' type int.

Here is a simple solution that satisfies conditions of your assignment The program reads input line by line. At first it reads the first line with the number of the size of the map and converts it to an object of type size_t. Then it initializes the map of size n * n with characters '0' by default.

for ( size_t i = 0; i < n; i++ )
{
    std::memset( map[i], '0', n );
}

Adter that it reads each line with digits and copy it in the corresponding row of the map using standard C function std::memcpy

for ( size_t i = 0; i < n && std::getline( std::cin, line ); i++ )
{
    line = line.substr( 0, n );
    std::memcpy( map[i], line.c_str(), line.size() );
}

As the input can be erroneous and a line can contain more or less than n characters we extract from the read line exactly n characters and copy them in the row.

In fact after that the assignment is done. All you need is to compare each element inside the map that it greater than adjusted elements.

#include <iostream>
#include <string>
#include <cstring>

int main() 
{
    const size_t N = 100;
    char map[N][N];

    std::string line;
    std::getline( std::cin, line );

    size_t n = std::stoul( line );
    if ( N < n ) n = N;

    for ( size_t i = 0; i < n; i++ )
    {
        std::memset( map[i], '0', n );
    }

    for ( size_t i = 0; i < n && std::getline( std::cin, line ); i++ )
    {
        line = line.substr( 0, n );
        std::memcpy( map[i], line.c_str(), line.size() );
    }

    std::cout << n << std::endl;
    for ( size_t i = 0; i < n; i++ )
    {
        for ( size_t j = 0; j < n; j++ ) std::cout << map[i][j] << ' ';
        std::cout << std::endl;
    }
    std::cout << std::endl;

    for ( size_t i = 1; i + 1 < n; i++ )
    {
        for ( size_t j = 1; j + 1 < n; j++ )
        {
            if ( map[i][j-1] < map[i][j] &&
                 map[i][j+1] < map[i][j] &&
                 map[i-1][j] < map[i][j] &&
                 map[i+1][j] < map[i][j] )
            {
                map[i][j] = 'X';
            }
        }
    }

    for ( size_t i = 0; i < n; i++ )
    {
        for ( size_t j = 0; j < n; j++ ) std::cout << map[i][j] << ' ';
        std::cout << std::endl;
    }
    std::cout << std::endl;

    return 0;
}

The output is

4
1 1 1 2 
1 9 1 2 
1 8 9 2 
1 2 3 4 

1 1 1 2 
1 X 1 2 
1 8 X 2 
1 2 3 4