Оптимизация & quot; Это Великий тыквенный патч & quot; ACM 1999 Практика

Итак, это еженедельный проект для школы, и у меня он полностью работает, но мне кажется, что способ, которым я это сделал, вероятно, не является одним из лучших способов сделать это (или даже хорошим способом). Я надеялся, что вы, ребята, могли бы помочь оптимизировать это / дать лучшее решение. Я уже представил эту версию, но хотел бы узнать более оптимальное решение проблемы.

Итак, для начала, вот проблема …

Почти Хэллоуин, и Линус отправляется в сад ждать Великую тыкву. К сожалению, из-за диверсификации в этом году в саду появилось много других тыкв, поэтому ему нужно, чтобы вы написали программу, рассказывающую ему, сколько там тыквенных пятен и насколько они велики.

Вход в эту программу будет ряд различных садов. В первой строке ввода для каждого сада будут указаны размеры сада, r, количество рядов в саду и c, количество столбцов, где 0 ≤ r ≤ 40 и 0 ≤ c ≤ 40. После размеры будут r строк с c символами на каждой строке. Каждый из этих символов будет строчной буквой, обозначающей тип тыквы, выращенной на площади. Строчная буква «р» будет представлять тыквы. Сад с 0 для числа строк и / или столбцов указывает на конец ввода и не должен обрабатываться.

Пример ввода:

10 10
pzzzzzzzzp
pyypzzzzzy
ppppssssyy
ssspssssyy
ssssppssyy
ssssppsspy
zzzzzzsspy
zzzzzzsspy
yyyypzsspy
yyyypppppy
3 4
pppp
pppp
pppp
1 7
zzzzzzz
0 0

Для каждого сада выведите номер сада (с первым входным набором, равным саду 1), количество тыквенных пятен в саду и размер тыквенных пятен в порядке от наименьшего к наибольшему. Если имеется более одного патча данного размера, напечатайте размер столько раз, сколько это происходит. Используйте следующий формат:

Пример вывода:

Garden # 1: 4 patches, sizes: 1 4 8 10
Garden # 2: 1 patches, sizes: 12
Garden # 3: 0 patches, sizes:

Примечание. Несмотря на то, что проблема говорит о вводе из файла, наш профессор велел нам вводить данные с клавиатуры.

Мой подход к этому состоял в том, чтобы поместить сад в двумерный массив с границей х вокруг. Затем я использовал бы функцию, чтобы найти тыквенный патч (и вернуть его координаты). Затем я использовал бы другую функцию, которая рекурсивно находила бы, если к ней была присоединена тыква, сверху, снизу, слева и справа и возвращала размер тыквенного пятна. Эта функция также «удаляет» каждую тыкву, когда находит, заменяя ее на «х». Это позволило мне не беспокоиться о поиске тыкв несколько раз.

Итак, вот мой код, довольно хорошо прокомментированный, чтобы вы, ребята, могли надеяться, что поняли, что я пытался сделать.

#include <iostream>
#include <fstream>

using namespace std;

const int MAX_ROW = 41;
const int MAX_COL = 41;

char input ();

int checkForPatchSize ( char arr[][MAX_COL], int numOne, int numTwo );

bool findPatch ( char arr[][MAX_COL], int &row, int&col );

void sort ( int arr[], int size);

int main ()
{
int inputNumOne = -1;  // Defaulted to -1, First number for Patch Size
int inputNumTwo = -1;  // Defaulted to -1, Second number for Patch Size
int i, j;      // i, j are indexes for loops, number
int numArr[MAX_ROW][MAX_COL]; // Array for storing Data
int indexGarden = 0;
int index = 1;

while ( inputNumOne != 0 )
{
cin >> inputNumOne;       // User inputs Dimension
cin >> inputNumTwo;       // Of Garden...
if ( inputNumOne != 0 and inputNumTwo != 0 )   // End case is that both are 0.
{
char pumpkinPatch[MAX_ROW][MAX_COL];   // Array for storing pumpkin patch info.
for ( i = 0; i < inputNumOne+2; i++ )
{
for ( j = 0; j < inputNumTwo+2; j++ )
{
// This if statement surrounds the garden in X's so that I have a border (allows me to not have to worry about test cases.
if ( i == 0 or j == 0 or i == inputNumOne + 1 or j == inputNumTwo + 1 )
{
pumpkinPatch[i][j] = 'x';
}
else   // This is the input of the garden into a 2d array.
{
pumpkinPatch[i][j] = input();
}
}

}int row, col, size, numberOfPatches = 0;
bool foundPatch = true;
index = 1;

while ( foundPatch == true )
{
row = inputNumOne+2;  // Because I added a border to the garden
col = inputNumTwo+2;  // the size is +2 of what the user input.
foundPatch = findPatch ( pumpkinPatch, row, col );  // Finds the start of a pumpkin patch, and returns the coordinates ( as row and col ).
if ( foundPatch == true ) // If a patch is found....
{
numberOfPatches++;  // Increase number of patches
size = checkForPatchSize ( pumpkinPatch, row, col); // find size of particular patch
numArr[indexGarden][index] = size; // put size into data arr (to be printed to screen later).
index++;}

}
numArr[indexGarden][0] = numberOfPatches; // Put number of patches as first item in each column of data arr.
indexGarden++;}

}

for ( index = 0; index < indexGarden; index++ ) // Print out Garden Info
{
cout << "Garden # " << index + 1 <<": " << numArr[index][0] << " patches, sizes: ";
int temp = numArr[index][0]; // temp is the number of patches in particular garden.
int tempArr[temp];   // temp array to be used for sorting
int indexTwo;
for ( indexTwo = 0; indexTwo < temp; indexTwo++ )
{
tempArr[indexTwo] = numArr[index][indexTwo+1];   // Transfer sizes into a temp array so that they can be sorted.

}
sort (tempArr, temp);  // Sort ( Sorts arr from smalles to larges )

for ( indexTwo = 0; indexTwo < temp; indexTwo++ )  // Output sorted array to screen.
{
cout << tempArr[indexTwo] << " ";
}

cout << endl;
}

}

char input()
{
char letter;
cin >> letter;
return letter;
}
/////////////// findPatch /////////////////////////////////////////////////
// Requirements: a 2D array of garden, and the size of it (row and col). //
// Returns a bool, true if patch is found, false if no patches found.    //
// row and col are returned by reference to be the coordinates of one    //
//  of the pumpkins in the patch.                                    //
///////////////////////////////////////////////////////////////////////////
bool findPatch ( char arr[][MAX_COL], int &row, int&col )
{
int rowIndex = 0;
int colIndex = 0;

while ( arr[rowIndex][colIndex] != 'p' and rowIndex < row )
{
colIndex = 0;
while ( arr[rowIndex][colIndex] != 'p' and colIndex < col )
{
colIndex++;
}
if ( arr[rowIndex][colIndex] != 'p' )
{
rowIndex++;
}
}

if ( arr[rowIndex][colIndex] != 'p' )
{
return false;
}
row = rowIndex;
col = colIndex;
return true;

}

/////////////// checkForPatchSize /////////////////////////////////////////
// Requirements: a 2D array of garden, and the coordinates of the start  //
//                 of a patch.  (Gotten from findPatch)                  //
// Returns an int, which is the size of the patch found                  //
// All p's or pumpkins are changed to x's so that they are not used      //
//  multiple times.                                                  //
///////////////////////////////////////////////////////////////////////////
int checkForPatchSize ( char arr[][MAX_COL], int numOne, int numTwo )
{
int index = 0;if ( arr[numOne][numTwo] == 'p' )
{
index++;
arr[numOne][numTwo] = '0';

// Check Above
index += checkForPatchSize ( arr, numOne - 1, numTwo );

// Check to Left
index += checkForPatchSize ( arr, numOne, numTwo - 1 );

// Check Below
index += checkForPatchSize ( arr, numOne + 1, numTwo );

// Check to Right
index += checkForPatchSize ( arr, numOne, numTwo + 1 );

return index;
}

return 0;
}
/////////////// sort //////////////////////////////////////////////////////
// Requirements: an integer array, and the size of it (amount of         //
//               numbers in it).                                         //
//                                                                       //
// Sorts an array from smalles to largest numbers                        //
///////////////////////////////////////////////////////////////////////////
void sort ( int arr[], int size )
{
int index = 0;
bool changeMade = true;

while ( changeMade == true )
{
changeMade = false;
for ( index = 0; index < size - 1; index++ )
{
if ( arr[index] > arr[index+1] )
{
int temp = arr[index];
arr[index] = arr[index+1];
arr[index+1] = temp;
changeMade = true;
}
}

}
}