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