3
\$\begingroup\$

I'm new to C++ (not to programming in general), which I want to learn to participate in some programming contests.

I solved the Online Judge Minesweeper Challange.

Since I'm not familiar with C++, any feedback (including nitpicking) is very welcome.

My algorithm:

For each field...

  1. Read the dimensions and initialize a 2d-array.
  2. Simultainiously read and parse the cells:
    1. If it's not a bomb, continue.
    2. Otherwise, set the cell to a negative value, then increase all existing, non-negative neighbours.
  3. Print each value, * for negative numbers (i.e. bombs).

I considered to separate the reading and parsing parts, but then I'd need to traverse the array once more.

#include <iostream>
using namespace std;

int **parseField(int n, int m);
void printField(int **field, int fieldIndex, int n, int m);

int main()
{
    int n, m, fieldIndex = 1;
    while (cin >> n >> m && !(n == 0 && m == 0))
    {
        if (fieldIndex > 1)
            cout << endl;
        int **field = parseField(n, m);
        printField(field, fieldIndex++, n, m);
    }
}

int **parseField(int n, int m)
{
    int **field = new int *[n];
    for (int i = 0; i < n; i++)
        field[i] = new int[m];

    string line;

    for (int i = 0; i < n; i++)
    {
        cin >> line;
        for (int j = 0; j < m; j++)
        {
            if (line[j] != '*')
                continue;

            field[i][j] = -1;

            for (int k = 0; k < 9; k++)
            {
                int x = i + (k / 3) - 1, y = j + (k % 3) - 1;
                if (x < 0 || x >= n || y < 0 || y >= m)
                    continue;
                if (field[x][y] >= 0)
                    field[x][y]++;
            }
        }
    }

    return field;
}

void printField(int **field, int fieldIndex, int n, int m)
{
    cout << "Field #" << fieldIndex << ":" << endl;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (field[i][j] < 0)
                cout << '*';
            else
                cout << field[i][j];
        }
        cout << endl;
    }
}
\$\endgroup\$
2
3
\$\begingroup\$

Don’t write using namespace std;.

You can, however, in a CPP file (not H file) or inside a function put individual using std::string; etc. (See SF.7.)


The style in C++ is to put the * or & with the type, not the identifier. This is called out specifically near the beginning of Stroustrup’s first book, and is an intentional difference from C style.


Put the functions in the opposite order, so you don't need to forward-declare them. Note that C++ has overloading, so if your declaration at the top doesn't match the actual function you'll get confusing link-time errors and not a compiler error for this file!


Don't use new. See ⧺C.149 — no naked new or delete. Use a std::vector here.

You are leaking memory: I don't see any delete!

int **field = parseField(n, m);
printField(field, fieldIndex++, n, m);

Every time through the loop, you are dropping field on the floor.


int n, m, fieldIndex = 1;
Don't declare multiple variables in one statement. Don't declare all your variables at the top, but declare where first needed and when you are ready to give it a value.

Here, the nature of cin input means you have to declare m and n before making that call. That's not the usual case.

architectural

Your parse and print are being passed the raw pointer thing, and the two sizes. Those should be combined into a single data structure, say a class named Field. Then these two function can be member functions of that class.

Your data structure is laborious and unnecessary. Back it with a std::vector<int>, and also store the height and width, all as members of the class. Write a lookup function that takes two indexes (r,c) and calculates a linear value r*width+c and feeds that to the underlying vector.

Use a type alias for the cell type rather than int. You can easily change it to (say) int8_t and see if it's faster as well as smaller.

\$\endgroup\$
3
\$\begingroup\$

Nit-Picking: You have come to the correct place


First, your whole style is more C rather C++ like. I don't see any abstraction or encapsulation.

Though, C++ can include C as (mostly) a subset. The styles of how the language is used are different. This is C like more than C++ like. The things that stand out are:

  • passing pointers (C++ prefers references or smart pointer or containers).
  • const correctness (Adding this later is a pain, so do it upfront).
  • Abstraction (Wrap your data in a class)

Memory Management.

Total fail you leak memory. For every new, there should be a call to delete. Or you should use higher-level constructs to handle the memory management automatically. If you want fast sure use C to avoid this.


Arrays:

Speed:

You use an array of arrays.
Why not allocate an n*m block of integers than calculate the position in the block. This will save on allocation time and be faster on lookup.

Support:

In C++ we don't usually manually allocate memory like this. It is easier (and safer) to use the existing containers. So I would use std::vector<int> to handle the memory allocation for me.


NitPick Section

Don't do this:

using namespace std;

Bad habit. Even doing this is a source file is bad. It will eventually come back to bite you.

see: Why is "using namespace std;" considered bad practice?


Sure looks very C like interface:

int **parseField(int n, int m);
void printField(int **field, int fieldIndex, int n, int m);

I would have written it like this:

class Data
{
    public:
        Data(int n, int m);
        print(int fieldIndex);
};

No need to accidentally pass in the wrong n and m values to the second function when you know they are going to be the same for both calls.


One line per variable please.

    int n, m, fieldIndex = 1;

This is just lazy. Also it makes it harder to read and has no real benefit.


That's a bit hard to read.

    while (cin >> n >> m && !(n == 0 && m == 0))

Use the Self Documenting Code principle.

    while (cin >> n >> m && isValidSize(n, m))

Always use braces around sub blocks (even if they are one line).

        if (fieldIndex > 1)
            cout << endl;

This will save you from so many mistakes in the long term. I just wish it was a required part of the language.

        if (fieldIndex > 1) {
            cout << endl;
        }

This is a performance issue.

            cout << endl;

The std::endl puts a newline character onto the stream then flushes the stream. Forcing the stream to flush is expensive. You should not be doing this unless there is a very good reason. The system will do this automatically when a flush is needed so there is rarely a need for you to do it.

Replace with:

            cout << "\n";  // Yes use a string.
                           // If you try and print a character it
                           // builds a string internally making it
                           // slower.

This the C way of declaring a variable:

        int **field = parseField(n, m);

In C++ types are much more important than in C. As a result, we keep all the type information together:

        int**   field = parseField(n, m);

I don't see a delete for this:

    int **field = new int *[n];

You may be saying to yourself well I did not want to do that because of speed. I am not sure that's a good argument. Because each time through the while loop in main you are allocating a field. So you are doing a whole bunch of memory allocation (which is the expensive part). Deallocation though not free is relatively cheap in comparison (nothing in the standard requires this,but it is what I have seen from looking at implementations of memory managers (you keep lists of similar sized objects that have been deleted for potential reuse)).

C++ designers realized a long time ago that objects are often reused a lot (or objects of a similar size are re-used a lot). As a result the memory management can (in good implementations) keep track of recently deleted objects under the assumption that they will quickly be reused. In this design I can quite easily see a lot of same size (or similar size) arrays being allocated and the memory management could take advantage of this to make the reallocation quicker than if the memory was split out of the main resevour.

But as always worth testing.


Prefer the prefix ++.

    for (int i = 0; i < n; i++)

Try this:

    for (int i = 0; i < n; ++i)

For integers, there is absolutely no difference. But in C++ we use iterators a lot. Iterators are not always pointers they can be objects so the prefix version is slightly faster (because of the standard pattern of how they are written).

So prefer to always use the prefix version that way you always get the optimal increment technique no matter what the type. Since a lot of times changes to C++ are simply changing a type (without changing any other code) this means your code will continue to be optimal.

see: How to overload the operator++ in two different ways for postfix a++ and prefix ++a?


How I would do it:

#include <memory>
#include <iostream>
#include <vector>


// Each member of the grid is either a mine
// which is printed as a '*' or empty which is represented by a number.
struct MineCount
{
    bool    mine;
    int     count;
};

// We need to save the size of the grid.
using Size = std::pair<int, int>;

// MineField
// Knows about mines and counts only.
//
// The maximum size of the field is [100 * 100]
// But to maximize speed we use contiguous piece of memory
// rather than an array of arrays. This reduces the cost
// of memory access as we only have to do one accesses to get
// the required location.
//
// To simplify the code we add a border of cells around the
// minefield. So all accesses to the grid is increment by 1
// in both X and Y dimensions. This allows us to increment
// the count in all adjoining fields without having to check if
// we are on the border of the field and thus incrementing
// beyond the edge of the array
//
// This should make the code faster and simpler to read.
class MineField
{
    Size                    size;
    std::vector<MineCount>  mines;

    static constexpr int    maxSize = 103;

    int index(int x, int y) {return x + (y * maxSize);}
    public:
        MineField()
            : size{0, 0}
            , mines(maxSize * maxSize)
        {}

        // Re-Use a minefield.
        // Reset only the state needed (previously used).
        // without having to reallocate the array.
        void reset(int n, int m)
        {
            for(int xLoop = 0; xLoop < size.first; ++xLoop) {
                for(int yLoop = 0; yLoop < size.second; ++ yLoop) {
                    mines[index(xLoop, yLoop)] = {false, 0};
                }
            }
            // Store Size +2 as we have an extra border around
            // the field.
            size.first = n + 2;
            size.second = m + 2;
        }
        // Add a mine to location X, Y
        void add(int x, int y)
        {
            ++x;
            ++y;

            // We have a mine in this square.
            mines[index(x, y)].mine = true;

            // Increment the count of all surrounding squares.
            // I was tempted to manually onroll this loop.
            for(int xLoop = -1; xLoop < 2; ++xLoop) {
                for(int yLoop = -1; yLoop < 2; ++yLoop) {
                    ++mines[index(x + xLoop, y + yLoop)].count;
                }
            }
        }

        // Get the character for a specific location.
        char get(int x, int y) const
        {
            ++x;
            ++y;

            if (mines[index(x, y)].mine) {
                return '*';
            }
            return '0' + mines[index(x, y)].count;
        }
};

// Wrapper class that understands about reading and writing
// to a stream for a minefield.
// This class does not know about the extra border on the field.
class Field
{
    Size        size;
    MineField   mineField;
    public:
        void reset(int n, int m);

        // Functionality to read and write. :-)
        void read(std::istream& stream);
        void write(std::ostream& stream) const;

        // Standard friend functions to make
        // reading and writting look like C++.
        friend std::istream& operator>>(std::istream& stream, Field& data) {
            data.read(stream);
            return stream;
        }
        friend std::ostream& operator<<(std::ostream& stream, Field const& data) {
            data.write(stream);
            return stream;
        }
};

void Field::reset(int n, int m)
{
    size = {n, m};
    mineField.reset(n, m);
}

void Field::read(std::istream& stream)
{
    // Assumes input file is correctly formatted.
    // The operator>> will ignore white space so we
    // don't need to deal with new line characters.
    // You can probably make it faster by manually handling this.
    for(int y = 0; y < size.second; ++y) {
        for(int x = 0; x < size.first; ++x) {
            char c;
            std::cin >> c;
            // Only care about '*'
            // Everything else is a '.' and can be ignored.
            if (c == '*') {
                mineField.add(x, y);
            }
        }
    }
}
void Field::write(std::ostream& stream) const
{
    for(int y = 0; y < size.second; ++y) {
        for(int x = 0; x < size.first; ++x) {
            std::cout << mineField.get(x, y);
        }
        stream << "\n";
    }
}

bool isField(int n, int m)
{
    return n != 0 && m != 0;
}

int main()
{
    // Only allocate the memory once.
    // Will reuse inside the loop by calling reset.
    Field   field;
    int     loop  = 0;

    int n;
    int m;

    while (std::cin >> n >> m && isField(n,m)) {
        // Reset then read the new field.
        field.reset(m, n);
        std::cin >> field;

        // The Judge does not want a trailing empty line.
        // So print it before each new field. But not before
        // the first one.
        if (loop != 0) {
            std::cout << "\n";
        }
        // Increment count and output.
        ++loop;
        std::cout << "Field #" << loop << ":\n"
                  << field;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.