5
\$\begingroup\$

Saw this question and though I wanted to try.

So my version of reading Mine Sweeper: For the Online Judge

Some Utilities Classes

#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>;

The MineField class

// 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;
        }
};

The Field class

// 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";
    }
}

Main

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\$

1 Answer 1

6
\$\begingroup\$

It looks good to me, but there are a few things I would suggest changing.

Make index static

The index function only uses maxSize from the class and does not alter the class, so I would suggest making it static.

Prefer a std::array to std::vector when the size is known

Because we don't do any dynamic resizing of the mines data member, it would be sensible to make it a std::array instead of a std::vector.

Fix the bug

The Field::read() function is correctly taking a std::istream& as a parameter, but is using std::cin instead of the passed stream. A similar error exists in Field::write().

Consider using a custom allocator

The use of field.reset inside the loop isn't too terrible, but without knowing what is behind the Field type, I'd more likely have simply made it a local variable within the loop. We can get the best of both worlds by creating a custom allocator for the Field class that does essentially what reset is doing, but without disturbing a more intuitive user interface.

Consider processing on the fly

Each mine affects exactly three rows; the row it's in and the rows above and below. With this observation, it's easy to see that by buffering only three rows, any size array could be processed on the fly as it is being read. This would reduce the memory requirement (although that wasn't large) and allow processing on the fly. Here's one way to do that: Yet another minesweeper field calculator

Consider changing the data format

Since the goal is to print each square as either a mine or a single digit, why not keep the data in text format? That way, each row could be kept as a std::string (or char *) and printed directly instead of requiring conversion.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.