Я застрял, пытаясь понять, как реализовать 2 функции для создания BFS с использованием std :: queue, который в конечном итоге считает острова. Причина, по которой я застрял, заключается в том, что я не понимаю, как правильно включить Position p0 и Matrix & Enclosure в функции. Может ли кто-нибудь pu sh в правильном направлении указать, как ссылаться на входные данные в fill и countTheIslands? Спасибо.
подсчет. cpp
#include "counting.h"
#include "matrix.h"
#include <list>
#include <queue>
using namespace std;
/**
* Count the number of islands (areas composed entirely of
* non-negative values connected either horizontally or
* vertically.
*
* @param enclosure a rectangular area of represented with -1 for water
* and zeros for land.
* @return the number of unconnected islands
*/
int countTheIslands (const Matrix<int>& enclosure)
{
// Should use the fill function
int count = 0;
for(int i=0; i < enclosure.length1(); i++){
for(int j=0; j< enclosure[i].length2(); j++){
if(enclosure[i][j] == 0){
count += fill(enclosure, i, j)
}
}
}
return count;
}
/**
* Starting at position p0, put valueToFill into that position and into
* any positions containing zero connected to p0 by one or more horizontal
* or vertical steps through other elements also containing zero.
*/
void fill (Matrix<int>& enclosure, int valueToFill, Position p0)
{
// Must use std::queue
}
counting.h
#ifndef COUNTING_H_
#define COUNTING_H_
#include <iostream>
#include "matrix.h"
struct Position {
int x;
int y;
};
inline
std::ostream& operator<< (std::ostream& out, Position p)
{
out << '(' << p.x << ',' << p.y << ')';
return out;
}
/**
* Count the number of islands (areas composed entirely of
* non-negative values connected either horizontally or
* vertically.
*
* @param enclosure a rectangular area of represented with -1 for water
* and zeros for land.
* @return the number of unconnected islands */
int countTheIslands (const Matrix<int>& enclosure);
/**
* Starting at position p0, put valueToFill into that position and into
* any positions containing zero connected to p0 by one or more horizontal
* or vertical steps through other elements also containing zero.
*/
void fill (Matrix<int>& enclosure, int valueToFill, Position p0);
#endif /* COUNTING_H_ */
matrix.h
#ifndef MATRIX_H
#define MATRIX_H
#include <algorithm>
#include <cassert>
template <class T>
class Matrix
//
// Provides a "2-dimensional" rectagular
// array-like structure for indexing using
// a pair of indices.
{
public:
Matrix();
Matrix (unsigned theLength1, unsigned theLength2);
Matrix (const Matrix<T>&);
~Matrix();
const Matrix<T>& operator= (const Matrix<T>&);
// Indexing into the matrix: What we would like to do is allow
// myMatrix[i,j]. But C++ allows operator[] only to take a single
// parameter. But operator() can take whatever parameters we like.
// So we can write myMatrix(i,j).
T& operator() (int i1, int i2);
const T& operator() (int i1, int i2) const;
unsigned length1() const;
unsigned length2() const;
bool operator== (const Matrix<T>&) const;
private:
T* data;
unsigned _length1;
unsigned _length2;
};
template <class T>
Matrix<T>::Matrix()
: data(0), _length1(0), _length2(0)
{}
template <class T>
Matrix<T>::Matrix(unsigned theLength1, unsigned theLength2)
: _length1(theLength1), _length2(theLength2)
{
data = new T[theLength1*theLength2];
}
template <class T>
Matrix<T>::Matrix(const Matrix<T>& m)
: _length1(m._length1), _length2(m._length2)
{
data = new T[_length1*_length2];
std::copy (m.data, m.data+_length1*_length2, data);
}
template <class T>
Matrix<T>::~Matrix()
{
delete [] data;
}
template <class T>
const Matrix<T>& Matrix<T>::operator= (const Matrix<T>& m)
{
if (this != &m)
{
if (_length1*_length2 < m._length1*m._length2)
{
delete [] data;
data = new T[m._length1*m._length2];
}
_length1 = m._length1;
_length2 = m._length2;
copy (m.data, m.data+_length1*_length2, data);
}
return *this;
}
// Indexing into the matrix: What we would like to do is allow
// myMatrix[i,j]. But C++ allows operator[] only to take a single
// parameter. But operator() can take whatever parameters we like.
// So we can write myMatrix(i,j).
template <class T>
T& Matrix<T>::operator() (int i1, int i2)
{
assert ((i1 >= 0) && ((unsigned)i1 < _length1));
assert ((i2 >= 0) && ((unsigned)i2 < _length2));
return data[i1 + _length1*i2];
}
template <class T>
const T& Matrix<T>::operator() (int i1, int i2) const
{
assert ((i1 >= 0) && (i1 < _length1));
assert ((i2 >= 0) && (i2 < _length2));
return data[i1 + _length1*i2];
}
template <class T>
inline
unsigned Matrix<T>::length1() const
{
return _length1;
}
template <class T>
inline
unsigned Matrix<T>::length2() const
{
return _length2;
}
template <class T>
bool Matrix<T>::operator== (const Matrix<T>& m) const
{
return (_length1 == m._length1)
&& (_length2 == m._length2)
&& equal (data, data+_length1*_length2, m.data);
}
#endif
jackalope. cpp
#include <iostream>
#include <fstream>
#include <string>
#include "matrix.h"
#include "counting.h"
using namespace std;
void solve (const Matrix<int>& enclosure)
{
int c = countTheIslands(enclosure);
cout << "The zoo can keep " << c << " jackalopes." << endl;
}
void readFrom(istream& in)
{
int width, height;
in >> width >> height;
Matrix<int> enclosure(width, height);
string line;
getline (in, line); // discard the first end-of-line
for (int y = 0; y < height; ++y)
{
getline (in, line);
for (int x = 0; x < width; ++x)
{
int terrain = 0;
if (line[x] == 'x' || line[x] == 'X')
terrain = -1;
enclosure(x,y) = terrain;
}
}
solve (enclosure);
}
int main (int argc, char** argv)
{
{
if (argc > 1)
{
ifstream in (argv[1]);
readFrom(in);
}
else
{
readFrom (cin);
}
}
return 0;
}