二维数组的沙漏总和 [英] Hourglass sum in 2D array

问题描述

我们得到了一个(6 * 6)二维数组，我们必须在其中找到一个最大的沙漏总和. 例如，如果我们在一个由零组成的数组中使用数字1创建一个沙漏，则它看起来可能像这样:

We are given a (6*6) 2D array of which we have to find largest sum of a hourglass in it. For example, if we create an hourglass using the number 1 within an array full of zeros, it may look like this:

沙漏的总和是其中所有数字的总和.上面的沙漏的总和分别为7、4和2.

The sum of an hourglass is the sum of all the numbers within it. The sum for the hourglasses above are 7, 4, and 2, respectively.

我为它编写了如下代码.这基本上是一个竞争性的编程问题，由于我是该领域的新手，我编写的代码具有非常糟糕的复杂性.在规定的时间内达到预期的输出.下面是我的代码:

I had written a code for it as follows.It is basically a competitive programming question and as I am new to the field,I have written the code with a very bad compplexity..perhaps so much that the program could not produce the desired output within the stipulated period of time.Below is my code:

    int main(){
    vector< vector<int> > arr(6,vector<int>(6));
    for(int arr_i = 0;arr_i < 6;arr_i++)
    {
      for(int arr_j = 0;arr_j < 6;arr_j++)
       {
        cin >> arr[arr_i][arr_j];
       }
    } //numbers input

    int temp; //temporary sum storing variable
    int sum=INT_MIN; //largest sum storing variable
    for(int i=0;i+2<6;i++) //check if at least3 exist at bottom
     { 
       int c=0; //starting point of traversing column wise for row

       while(c+2<6) //three columns exist ahead from index
        {  
          int f=0; //test case variable
          while(f!=1)  
          { //if array does not meet requirements,no need of more execution  

            for(int j=c;j<=j+2;j++)
             { //1st and 3rd row middle element is 0 and 2nd row is non 0.
               //condition for hourglass stucture                    
             if((j-c)%2==0 && arr[i+1][j]==0||((j-c)%2==1 && arr[i+1][j]!=0)
             //storing 3 dimensional subarray sum column wise               
             temp+=arr[i][j]+arr[i+1][j]+arr[i+2][j]; //sum storage 
             else
             f=1; //end traversing further on failure


              if(sum<temp)
              sum=temp;

              f=1;//exit condition
              }//whiel loop of test variable 

             temp=0; //reset for next subarray execution
             c++; /*begin traversal from one index greater column wise till 
                    condition*/
              }// while loop of c
        } 
      }       

          cout<<sum;

         return 0;
    }

这是我在时间间隔内无法处理的代码的实现.请考虑时间的复杂性，提出一个更好的解决方案，并随意指出我在理解问题上的任何错误.问题来自Hackerrank. 如果您仍然需要此链接，请访问以下链接: https://www.hackerrank.com/challenges/2d-array

This is my implementation of the code which failed to process in the time interval.Please suggest a better solution considering the time complexity and feel free to point out any mistakes from my side in understanding the problem.The question is from Hackerrank. Here is the link if you need it anyways: https://www.hackerrank.com/challenges/2d-array

推荐答案

您的问题的解决方案是:

The solution for your problem is:

#include <cstdio>
#include <iostream>
#include <climits>

int main() {
    int m[6][6];

    // Read 2D Matrix-Array
    for (int i = 0; i < 6; ++i) {
        for (int j = 0; j < 6; ++j) {
            std:: cin >> m[i][j];
        }
    }

    // Compute the sum of hourglasses
    long temp_sum = 0, MaxSum = LONG_MIN;
    for (int i = 0; i < 6; ++i) {
        for (int j = 0; j < 6; ++j) {
            if (j + 2 < 6 && i + 2 < 6) {
                temp_sum = m[i][j] + m[i][j + 1] + m[i][j + 2] + m[i + 1][j + 1] + m[i + 2][j] + m[i + 2][j + 1] + m[i + 2][j + 2];
                if (temp_sum >= MaxSum) {
                    MaxSum = temp_sum;
                }
            }
        }
    }
    fprintf(stderr, "Max Sum: %ld\n", MaxSum);

    return 0;
}

该算法很简单，它对左上角开始的所有沙漏进行求和，并且由于无法形成沙漏，因此未处理最后2列和2行.

The algorithm is simple, it sums all the Hourglasses starting of the upper left corner and the last 2 columns and 2 rows are not processed because it can not form hourglasses.

这篇关于二维数组的沙漏总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！