РЕДАКТИРОВАТЬ Я заметил небольшую ошибку в этой программе: - когда я представил ее изначально, это было сделано только для одного теста;Затем я вернулся к своей среде IDE, чтобы улучшить алгоритм работы с несколькими тестовыми примерами.После того, как я заработал, я вернулся сюда, чтобы отредактировать этот пост, и я пропустил пару важных строк.Теперь они исправлены, и я также добавил несколько комментариев о том, что еще можно добавить в этот класс, если кто-то хочет сохранить связанную запись каждого теста вместе с соответствующим значением штрафа. End Edit
Я инкапсулировал это в класс.Я почти уверен, что, возможно, есть более элегантный способ сделать это, но это то, что я придумал, используя ваш пример текстового файла для заполнения структуры данных и метод возврата штрафов.
pcs.txt
1
15 8 3
3 8
11 2
8 6
DefenderBoard.h
#ifndef DEFENDER_BOARD_H
#define DEFENDER_BOARD_H
#include <fstream>
#include <vector>
#include <algorithm>
struct Coord {
unsigned x;
unsigned y;
Coord() : x(0), y(0) {}
Coord( unsigned xIn, unsigned yIn ) : x( xIn ), y( yIn ) {}
};
class DefenderBoard {
private:
std::string filename;
unsigned testcase;
unsigned gridsize_x;
unsigned gridsize_y;
unsigned numTowers;
std::vector<unsigned> penalties;
std::vector<Coord> cells;
public:
explicit DefenderBoard( const std::string& filenameIn );
~DefenderBoard();
void getPenalties( std::vector<unsigned>& penalties ) const;
private:
void getDataFromFile();
void calculatePenalty();
};
#endif // DEFENDER_BOARD_H
DefenderBoard.cpp
#include "DefenderBoard.h"
DefenderBoard::DefenderBoard( const std::string& filenameIn ) :
filename( filenameIn ),
gridsize_x( 0 ), gridsize_y( 0 ),
testcase( 0 ),
numTowers( 0 ),
penalty( 0 ) {
getDataFromFile();
}
DefenderBoard::~DefenderBoard() {
}
void DefenderBoard::getPenalties( std::vector<unsigned>& penaltiesOut ) const {
penaltiesOut = penalties;
}
void DefenderBoard::getDataFromFile() {
std::ifstream file;
file.open( filename );
if ( !file.is_open() ) {
// Note: This ExceptionHandler will not work for you.
// You will need to supply your own error or exception handling.
std::ostringstream strStream;
strStream << __FUNCTION__ << " failed to read in file[" << filename << "]";
throw ExceptionHandler( strStream );
}
file >> testcase;
// Temps
Coord towerCoord;
// t -> testcase | c - tower coords
for ( unsigned t = 0; t < testcase; ++t ) {
file >> gridsize_x;
file >> gridsize_y;
file >> numTowers;
for ( unsigned c = 0; c < numTowers; ++c ) {
file >> towerCoord.x;
file >> towerCoord.y;
cells.push_back( towerCoord );
}
calculatePenalty();
// After Penalty is calculated this test case along with the penalty value
// can be stored into a struct containing both the penalty and a vector of cells
// which would be done here and then that struct would be stored into another container to this class
// If the above is choosen to be done then this needs to be called here instead of within the calculate function
// Clear our cells so it can be reused for each test case found in this file.
cells.clear();
}
file.close();
}
bool compareCoordsX( const struct Coord& a, const struct Coord& b ) {
return a.x > b.x;
}
bool compareCoordsY( const struct Coord& a, const struct Coord& b ) {
return a.y > b.y;
}
void DefenderBoard::calculatePenalty() {
std::vector<unsigned> xValDiff;
std::vector<unsigned> yValDiff;
unsigned diff = 0;
// First Sort By Largest X - Then Find The Differences
std::stable_sort( cells.begin(), cells.end(), compareCoordsX );
unsigned idx = 0;
for ( ; idx < cells.size(); ++idx ) {
// For First Iteration Only
if ( idx == 0 ) {
diff = gridsize_x - cells[idx].x;
xValDiff.push_back( diff );
} else {
diff = cells[idx-1].x - cells[idx].x - 1; // Don't Forget to Subract 1
xValDiff.push_back( diff );
}
}
// Also push back the last value - 1
xValDiff.push_back( cells.back().x - 1 );
// Do Same Thing For Y
std::stable_sort( cells.begin(), cells.end(), compareCoordsY );
idx = 0;
diff = 0;
for ( ; idx < cells.size(); ++idx ) {
// First Iteration Only
if ( idx == 0 ) {
diff = gridsize_y - cells[idx].y;
yValDiff.push_back( diff );
} else {
diff = cells[idx-1].y - cells[idx].y - 1; // Don't Forget to Subtract 1
yValDiff.push_back( diff );
}
}
// Also push back the last value - 1
yValDiff.push_back( cells.back().y - 1 );
unsigned largestX = xValDiff[0];
unsigned largestY = yValDiff[0];
idx = 0;
for ( ; idx < cells.size(); ++idx ) {
if ( xValDiff[idx] > largestX ) {
largestX = xValDiff[idx];
}
if ( yValDiff[idx] > largestY ) {
largestY = yValDiff[idx];
}
}
// Calculate Penalty And Store It
// EDIT - I did update this code after I had originally posted it
// and when I added the update I did forget to change this commented section
// penalty = largestX * largestY;
// It should be like this:
penalties.push_back( largestX * largestY );
// I did have this line of code here too but I moved it out of this function and into the getDataFromFile() method.
// cells.clear();
}
main.cpp
#include <iostream>
#include "DefenderBoard.h"
int main() {
std::vector<unsigned> penalties;
DefenderBoard board( "pieces.txt" );
board.getPenalties( penalties );
unsigned idx = 0;
for ( ; idx < penalties.size(); ++idx ) {
std::cout << penalties[idx] << " ";
}
std::cout << std::endl;
return 0;
}
Выход
12
Второй запуск - два теста:
pcs.txt
2
15 8 3
3 8
11 2
8 6
12 10 4
2 2
9 7
3 9
8 5
Выход
12 8
Примечание: Нет проверки границ, чтобы увидеть, больше ли координата ячейки в файле, чем размер платы MxN.Так что, если размер сетки скажем 8x8, и есть фрагмент, имеющий координаты [12,2] или [5,9], это нарушит алгоритм и даст вам недействительные результаты.Я оставлю эти случаи ошибок в качестве упражнения.
Реализация алгоритма Идея этого алгоритма состоит в том, чтобы сначала взять размер и вычесть самый дальний фрагмент.Затем вы возьмете это, вычтете из него следующий самый дальний кусок и отнимите 1, пока не достигнете последнего, затем, наконец, вы возьмете сам последний кусок и вычтете 1 из него.Это даст вам все различия в одном направлении.Повторите это и для другого направления.Тогда вы ищете самый большой размер как х, так и у.Если у вас есть все, что вам нужно, это рассчитать произведение наибольших различий в направлениях x и y, и это даст вам наибольшую открытую площадь.
Я также заметил, что в коде есть некоторый тип дублирования, который также может быть реорганизован путем добавления пары более мелких функций в класс, но для показа алгоритма я не думаю, что это действительно необходимов этом случае.Единственный двойной цикл for, который есть в этом алгоритме, - это чтение данных из файла.Фактический расчет работает от линейного вектора координатных пар.Есть 3 одиночных цикла for, которые пересекают векторы.Первые два одинаковы один раз в направлении х и один раз в направлении у.Таким образом, время основано на размере или длине входа N. Это должно быть постоянным временем.Последним циклом for по-прежнему будет N, но с учетом вектора размера N + 1, который все еще остается постоянным временем, где N - количество башен или координатных пар.Компромисс заключается в том, что из-за локальных векторов для хранения различий в значениях x & y существует небольшая перегрузка памяти, а для небольших и средних наборов данных это не должно вызывать беспокойства.
Отказ от ответственности
Это было упомянуто в комментарии к моему ответу:
Спасибо за усилия и извините, если это произойдетотрицательно ... но мне интересно, когда люди когда-либо будут преподавать этот тип "инкапсуляции" в "классы" как часть учебной программы ОО ... Это может быть моим личным вкусом, но частные функции-члены, не имеющие аргументов и возвращающие пустоту, являютсянесколько красный флаг для меня.При чтении кода необходимость отслеживать все члены, которые могут быть изменены, так же вредна, как наличие глобальных переменных, как в эпоху программированияИ в этом конкретном случае они помогают скрыть ошибку, что во втором тестовом примере используются обе башни из тестового примера 1 и 2
Да, в коде была ошибка, и я исправил ее, как указано выше.Теперь, если взглянуть на общий дизайн этого объекта класса или подхода ОО, они увидят, что реализация скрыта от пользователя или вызывающей стороны этого объекта класса.Существует определенный порядок того, что он здесь происходит.
Алгоритм в шагах
- Объявление объекта этого типа с помощью определяемого пользователем конструктора.
- Конструктор принимает строку для имени файла для чтения данных.
- Файл открывается, и в случае успеха он начинает читать данные, в противном случае выдается исключение.
- Он определяет, сколькосуществуют тестовые наборы, и для каждого тестового примера выполняется следующее:
- Извлекает количество башен.
- Получает координаты каждой башни в этом тестовом примере.
- Вычисляет штраф для всех башен этого тестового примера.
- Сохраняет значение штрафа для этого случая.
- Повторяет этот процесс для всех тестовых случаев.
- Закрывает поток файла.
- Построение объекта завершено.
- Теперь объект завершен, и единственное, что осталось - пользователь вызывает свой метод открытого интерфейса для получения штрафа.значения.
Дополнительные функции - их можно добавить -
- Проверка границ координат башни по размеру сетки MxN.
- Статистика всех случаев - повторения, среднее значение, медиана, режим, стандартное отклонение и т. Д.
- Встроенные методы печати.
- Дополнительный контейнер для хранения всех местоположений ячеек башни с соответствующими значениями штрафа для каждого тестового случая.
- Дополнительные проверки ошибок.
- Некоторые улучшения рефакторинга и эффективности.
Поправка Лисярус высказал хорошее замечание в комментариях и на основании этого здесь не OO-версия.
#include <string>
#include <vector>
#include <algorithm>
#include <fstream>
struct TowerCoordinate {
unsigned x;
unsigned y;
TowerCoordinate() : x(0), y(0) {}
TowerCoordinate( unsigned xIn, unsigned yIn ) : x( xIn ), y( yIn ) {}
};
struct GridSize {
unsigned width;
unsigned height;
GridSize() : width( 0 ), height( 0 ) {}
GridSize( unsigned widthIn, unsigned heightIn ) : width( widthIn ), height( heightIn ) {}
};
bool compareCoordsX( const struct TowerCoordinate& a, const struct TowerCoordinate& b ) {
return a.x > b.x;
}
bool compareCoordsY( const struct TowerCoordinate& a, const struct TowerCoordinate& b ) {
return a.y > b.y;
}
// Returns A Single Penalty
unsigned calculatePenalties( std::vector<TowerCoordinate>& towerLocations, GridSize& gridSize ) {
std::vector<unsigned> xValDiff, yValDiff;
unsigned diff = 0;
unsigned idx = 0;
// First Sort By Largest X - Then Find All Differences
std::stable_sort( towerLocations.begin(), towerLocations.end(), compareCoordsX );
for ( ; idx < towerLocations.size(); ++idx ) {
if ( idx == 0 ) {
diff = gridSize.width - towerLocations[idx].x;
xValDiff.push_back( diff );
} else {
diff = towerLocations[idx-1].x - towerLocations[idx].x - 1; // Don't Forget To Subtract 1
xValDiff.push_back( diff );
}
}
// Also Push Back (Last Value - 1)
xValDiff.push_back( towerLocations.back().x - 1 );
// Sort By Largest Y - Then Find All Differences
// First Sort By Largest X - Then Find All Differences
idx = 0;
diff = 0;
std::stable_sort( towerLocations.begin(), towerLocations.end(), compareCoordsY );
for ( ; idx < towerLocations.size(); ++idx ) {
if ( idx == 0 ) {
diff = gridSize.height - towerLocations[idx].y;
yValDiff.push_back( diff );
} else {
diff = towerLocations[idx-1].y - towerLocations[idx].y - 1; // Don't Forget To Subtract 1
yValDiff.push_back( diff );
}
}
// Also Push Back (Last Value - 1)
yValDiff.push_back( towerLocations.back().y - 1 );
unsigned largestX = xValDiff[0];
unsigned largestY = yValDiff[0];
idx = 0;
for ( ; idx < towerLocations.size(); ++idx ) {
if ( xValDiff[idx] > largestX ) {
largestX = xValDiff[idx];
}
if ( yValDiff[idx] > largestY ) {
largestY = yValDiff[idx];
}
}
return (largestX * largestY);
}
// Returns The Results Of All The Penalties For Each Case
std::vector<unsigned> getDefenderDataFromFile( const std::string& filename, unsigned& numTestCases, GridSize& gridSize, unsigned& numTowers, std::vector<TowerCoordinate>& towerLocations ) {
std::ifstream file;
file.open( filename );
if ( !file.is_open() ) {
// This ExceptionHandler will not work for you; you will need to supply your own error or exception handling.
std::ostringstream strStream;
strStream << __FUNCTION__ << " failed to read in file[" << filename << "]";
throw ExceptionHandler( strStream );
}
file >> numTestCases;
TowerCoordinate towerCoord;
std::vector<unsigned> penalties;
for ( unsigned t = 0; t < numTestCases; ++t ) {
file >> gridSize.width;
file >> gridSize.height;
file >> numTowers;
for ( unsigned c = 0; c < numTowers; ++c ) {
file >> towerCoord.x;
file >> towerCoord.y;
towerLocations.push_back( towerCoord );
}
unsigned currentPenalty = calculatePenalties( towerLocations, gridSize );
penalties.push_back( currentPenalty );
towerLocations.clear();
}
file.close();
return penalties;
}
int main() {
unsigned numTestCases = 0;
unsigned numTowers = 0;
GridSize gridSize;
std::vector<TowerCoordinate> towerLocations;
std::vector<unsigned> penalties;
penalties = getDefenderDataFromFile( "pieces.txt", numTestCases, gridSize, numTowers, towerLocations );
unsigned idx = 0;
for ( ; idx < penalties.size(); ++idx ) {
std::cout << penalties[idx] << " ";
}
std::cout << std::endl;
return 0;
}
Единственное, что нужно знать об этомтекущая реализация этого алгоритма заключается в том, что вектор местоположений башен очищается после каждого контрольного примера, поэтому, как только вы получите окончательные результаты всех штрафов, контейнер координат башен в текущем кадре стека будет состоять только из самого последнего набора позицийи не будет содержать каких-либо предыдущих их итераций.И снова нет проверки границ башни по размеру сетки.