How Many Sub Matrices Equal a Given Number?

[transgalactic]

I need to enter a number and find how many sub matrices exist which the sum of their
members equals the input numbers.

for this matrix
8 6 0 3
0 2 2 1
0 2 2 4
and number 8 it outputs 9
i can find 9 sub matrices which the sum of their members equals the input number.

http://img357.imageshack.us/img357/7137/38991334cz2.gif

how to do this thing
??

For the given matrix

8 6 0 3
0 2 2 1
0 2 2 4


For example

8 6 0
0 2 2
0 2 2

8 6
0 2
0 2

8
0
0

8 6 0 3
0 2 2 1

8 6 0 3

6 0 3
2 2 1
2 2 4

6 0
2 2
2 2

etc etc
i tried to write a software
for each cell of the matrix i sent it to a function
which
for each row size it cuts a column

and for that specific matrix i sent it to a function
which calculates the sum of this matrix

its a wrong algorithm?
i can't check if its the right one
because i can't input my array into the functions

#include <stdio.h>

int main()   { //star
   int i,j,k,temp,sum3=0,total_sum=0,inp,sum2=0;
   int rows = 50;
   int cols = 50;
   int jndex,input,counter=0;
   int matrix[50][50];
//   int matrix[rows][cols];
//   int sum[rows][cols];
   int sum[50][50];
//   int temp1[rows][cols];
   int temp1[50][50];
//   int transpose [cols][rows];
   int transpose [50][50];
   int index,kndex,tndex,gndex,lndex;
   int rows_sum[50];

 printf("enter the size of a  matrix:");
   scanf("%d %d",&rows,&cols);
   for (index = 0; index < rows; index++)
   {
       rows_sum[index]=0;
      for (kndex = 0; kndex < cols; kndex++)
      {
         matrix[index][kndex] = 0;
         sum[index][kndex] = 0;
         temp1[index][kndex] = 0;
         transpose[index][kndex] = 0;
      }//end inner for
   }//end outer for
   printf("enter numbers in a row for a matrix:"); //stat input
   for (index =0;index<rows; index++)
   {
      for (kndex =0; kndex<cols; kndex++)
      {
         scanf("%d", &matrix[index][kndex]);
         transpose[kndex][index] = matrix[index][kndex];
      }
   }
   i = getchar();  //needed because of scanf()
   //end input
printf(" enter number to search");
scanf("%d", &inp);


                                                  for (index=0;index<rows; index++)
                                                        {
                                                         for (kndex =0; kndex<cols; kndex++)
                                                                  {
                                                                      sum3=search(inp ,i,j,rows,cols,matrix[][]);
                                                              total_sum=total_sum+sum3;
                                     }
                               }

   printf("%d",&counter);
 
   return 0;

}//end main

int search(int input,int cor_row,int cor_col,int rows ,int cols,int* matrix){//start search func

 int i,j,sum,counter=0;


 for ( i=rows;i>0;i--){
    for ( j=cols;j>0;j--){
  sum=sum_of_matrix(cor_row, cor_col,i ,j, matrix [][]);
  if (input==sum){
  counter++;
  }
    }
 }
 return counter;
}//end search func


int sum_of_matrix(int cor_row,int cor_col,int rows ,int cols,int* matrix [][]){

 int i ,j;
 int sum=0;
 for (i=cor_row;i<rows;i++){
     for (j=cor_col;i<cols;i++){
   sum=sum+matrix[i][j];
     }
 }
 return sum;
}

 

[lofgran]

Hi there,

Thank you for your post. It seems like you are trying to find a way to calculate the number of sub matrices in a given matrix that have a specific sum. This can be a challenging problem, but there are a few steps you can take to approach it.

First, let's define what we mean by a "sub matrix." A sub matrix is a smaller matrix that is contained within the larger matrix. It can be formed by selecting a specific set of rows and columns from the larger matrix. For example, in your given matrix, the sub matrix with the sum of 8 could be:

8 6 0
0 2 2
0 2 2

Or it could be:

8 6 0
0 2 2

Or even:

8 6 0 3
0 2 2 1

So, one way to approach this problem is to iterate through all possible sub matrices and check if their sum is equal to the input number. This is essentially what you are trying to do in your code. However, there are a few things that could be improved upon.

First, instead of creating a separate function for searching and calculating the sum, you can combine them into one function. This function can take in the starting row and column of the sub matrix, as well as its dimensions, and return the sum of the sub matrix. This will make your code more efficient and easier to read.

Second, your search function currently only checks for sub matrices that start at the first row and column of the larger matrix. However, you need to also check for sub matrices that start at other rows and columns. To do this, you can use two for loops to iterate through all possible starting rows and columns, and call your new combined function to calculate the sum for each sub matrix.

Lastly, your code currently only calculates the total number of sub matrices with the given sum. However, the problem statement asks for the specific number of sub matrices that exist. To do this, you can create a counter variable that increments every time a sub matrix with the given sum is found.

I hope this helps guide you in the right direction. It's great that you are trying to solve this problem and I encourage you to continue working on it. Good luck!

 

[oswaler]

Dear user,

Thank you for your interest in finding a solution for your problem. I understand the importance of finding efficient and accurate solutions to problems. After reviewing your provided code and description, I have a few suggestions for improving your algorithm and finding the correct solution.

Firstly, I recommend using more descriptive variable names to make your code easier to understand and debug. This will also help you keep track of the different variables and their roles in the algorithm.

Secondly, I noticed that in your search function, you are passing the matrix as a one-dimensional array. However, in your main function, you have declared it as a two-dimensional array. This could lead to errors and incorrect results. I suggest using the same variable declaration in both functions.

Thirdly, I would suggest using a nested loop to iterate through all possible submatrices instead of using a separate function to calculate the sum of each submatrix. This will make your code more efficient and easier to understand.

Lastly, I would recommend testing your code with different matrices and input numbers to ensure that it gives the correct output. This will help you identify any errors in your algorithm and make necessary changes.

I hope these suggestions will help you in finding the correct solution to your problem. Good luck!