Searching the biggest value of 'H' shaped regions in a matrix

[vboro]

Hi!

I got the task where I must find the H shaped region which has the biggest sum of numbers in it. The 'H' shaped region is something like this:

x x
xxx
x x

The matrix's size must be 3*3 or bigger than that, and I don't have to work with rotated 'H' shape. However, it can move upwards and downwards if the matrix is that big (for example a 4*6 matrix).

I thought of first counting a "maximum" value, starting from the [0][0] element. However, I can't figure out how to move this region-counting along. Could you help me out, please?

Here's my code so far:

#include<iostream>

int main(){
	
	int n = 3;
	int m = 4;
	
	int mtx[n][m] = {
		1,1,1,3,
		1,1,1,3,
		1,1,1,3
	};
	
	//counting the maximum H value
	int min = 0;
	
	for(int i = 0; i < n; i++){
		max += mtx[i][0];
	}
	
	for(int i = 0; i < n; i++){
		max += mtx[i][2];
	}
	
	min += mtx[1][1];
	
	
	int counter = 0;
	int j = 0;
	int k = 0;
	
	//finding if there is bigger
	while(counter > max){
		
		if(counter < max){
			min = counter;
		}
	}
	
	return 0;
}

[lastchance]

Clarify what you mean by your "H shape."

Is it always 3x3? Is it always square? Are the vertical and horizontal bars always one element thick?

If not, what if the vertical sides of the H are, say, an even length - say 4? What is the position and what is the thickness of the horizontal bar in that case?

If you have an accessible specification of this problem please post it as original - NOT your rewording of it.

[vboro]

As I mentioned at the beginning, it's an area, which consist of 7 elements in a matrix:

x x
xxx
x x

It's always like this, there is no change in this H shape. The size of the matrix can change.

[TheIdeasMan]

@vboro

if you use the true type format TT on the format bar, the text will display better:

x x
xxx
x x

[vboro]

Ohh, I see, thanks for the tip :D

[lastchance]

vboro wrote:

I must find the H shaped region which has the biggest sum of numbers in it

In that case, I'm mystified by why you should be looking for the minimum of anything. Like I said: post your original problem. Unedited.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
   vector< vector<int> > mtx = { {1,1,1,3}, {1,1,1,3}, {1,1,1,3} };
   int rows = mtx.size(), cols = mtx[0].size();
   
   int maxH = 0;
   for ( int i = 1; i < rows - 1; i++ )
   {
      for ( int j = 1; j < cols - 1; j++ )
      {
         int H = mtx[i][j]
               + mtx[i-1][j-1] + mtx[i][j-1] + mtx[i+1][j-1]
               + mtx[i-1][j+1] + mtx[i][j+1] + mtx[i+1][j+1];
         if ( ( i == 1 && j == 1 ) || H > maxH ) maxH = H;
      }
   }
   cout << "Maximum H is " << maxH << '\n';
}

Maximum H is 13

[vboro]

Ohh, yes, I just noticed that I misstyped it ^^' Thanks for the notice and the help, too!!

[TomCPP]

See the following solution.

#include <iostream>
#include <vector>
#include <cassert>
#include <limits>

using namespace std;

using Matrix = vector<vector<int>>;

Matrix generate( int row , int column )
{
    Matrix result(row,vector<int>(column));
    for( auto& row : result )
    {
        for( auto& value : row ) value = rand()%20;
    }
    return result;
}

int sum_H_shape( const Matrix& matrix , int row , int column )
{
    int result {0};
    for( int width {0} ; width<3 ; ++width )
    {
        for( int height {0} ; height<3 ; ++height )
        {
            result += ( height == 1 && width != 1 ) ? 0 : matrix[row+width][column+height];
        }
    }
    return result;
}

int findMaximum( const Matrix& matrix )
{
    assert( matrix.size()>2 && matrix[0].size()>2 );

    int maximum {numeric_limits<int>::min()};    

    for( int posx {0} ; posx<matrix.size()-2 ; ++posx )
    {
        for( int posy {0} ; posy<matrix[0].size()-2 ; ++posy )
        {
            auto sum = sum_H_shape( matrix , posx , posy );            
            if( maximum < sum ) maximum = sum;
        }
    }   
    return maximum;
}

ostream& operator<<( ostream& out , const Matrix& matrix )
{
    for( const auto& row : matrix )
    {
        for( const auto& value : row ) out << value << '\t';
        out << endl;
    }
    return out;
}

int main()
{
   auto matrix = generate(5,7);
   cout << matrix << "\nmaximum is = " << findMaximum(matrix) << "\n";
}

https://godbolt.org/z/GdexejzeK

[jonnin]

there is probably some slick way to do it making use of overlapping, but summation is so cheap...