c++ - 优化 "It' 的 Great Pumpkin Patch。”ACM 1999 实践

Question

所以，这是学校的每周项目，我已经完全完成了，但感觉好像我做的方式可能不是最好的方式之一(甚至不是好的方式).我希望你们能帮助优化它/提供更好的解决方案。我已经提交了这个版本，但想知道一个更优化的问题解决方案。

---

所以首先，问题是...

It's almost Halloween and Linus is setting out to the garden to wait for the Great Pumpkin. Unfortunately, due to diversification, there are lots of other gourds in the garden this year, so he needs you to write a program to tell him how many patches of pumpkins there are and how big they are.

The input to this program will be a number of different gardens. The first line of the input for each garden will be the dimensions of the garden, r, the number of rows in the garden, and c, the number of columns, where 0 ≤ r ≤ 40 and 0 ≤ c ≤ 40. Following the dimensions will be r lines with c characters on each line. Each of these characters will be a lower case letter representing the type of gourd grown in the square. A lower case 'p' will represent pumpkins. A garden with 0 for the number of rows and/or columns indicates the end of input and should not be processed.

示例输入:

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

For each garden, output the number of the garden (with the first input set being garden 1), the number of pumpkin patches in the garden, and the size of the pumpkin patches in order from smallest to largest. If there is more than one patch of a given size, print the size as many times as it occurs. Use the following format:

示例输出:

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

注意:尽管问题说要从文件输入，但我们的教授告诉我们要通过键盘输入。

---

我的方法是将花园放入一个二维数组中，并在其周围有一个 x 的边框。然后我会使用一个函数来查找南瓜地(并返回其坐标)。然后，我将使用另一个函数，该函数通过上方、下方、左侧和右侧递归地查找南瓜是否附加到那个南瓜，并返回南瓜 block 的大小。此函数还会在找到南瓜时通过用“x”替换它来“删除”每个南瓜。这让我不必担心多次找到南瓜。

这是我的代码，注释得很好，这样你们就可以理解我正在尝试做的事情。

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

    }
}

Answer 1

好的，看完你的代码，我明白了你的做法。一般来说，我会从视觉角度来处理这个问题。实际上，您的代码应该可以正常工作，并且是一个非常优雅的解决方案。你的算法的唯一弱点是它每次移动时都会迭代同一个补丁。例如，当它向上移动时，它向下检查。避免冗余是最佳算法的最可靠标志，但就您部署算法的小规模而言，它不一定是最佳的。

在某种程度上，您的代码的递归性质使其非常漂亮，因为它像小 Spark 一样穿过南瓜地，然后熄灭，我真的很喜欢。递归是我不经常打扰自己的东西，主要是因为我不递归地思考，但是在花了一些时间思考你的算法之后，我确实看到了它在这种情况下的值(value)。我很乐意看到该算法与动态视觉效果一起工作。

至于你的算法的准确性，我无法想象它会以任何方式正确地计算南瓜数量，因为它的功能是在采摘的南瓜周围产生一个小波浪，算法在其中重复自身，有效地传播到补丁，直到它被全部计算在内。正如我所说，您的算法的唯一缺点是如果您没有以某种方式将南瓜标记为已找到(它会检查调用它的位置)，它将陷入无限循环。除此之外，我只能说你提出了一个很好的解决方案，你的疑虑几乎完全是错误的。在这方面使用递归算法是一个很好的选择，因为它不需要很长的案例列表来“计数”；它只是跳到相邻的位置，返回到自己的完整计数。