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