Thread: how to find a sub matrix..

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
its like artificial intelligence

i was given this example to act upon

http://img357.imageshack.us/my.php?i...8991334cz2.gif

those matrices could vary in size and shape
there are too many possibilities

??

cutting the matrix for each cell like it shows in the example
and comparing the sum with an input number
and printing the counter

but its not working
i get error like "ex2.exe encoutered an error"

i marked the searching part by comments
"start searching code"
"end searching code"

Code:

#include <stdio.h>

int main()   { //star
	int i,j,k,temp,inp,sum2=0;
	int rows = 50;
   int cols = 50;
   int jndex,input,counter=0;
//	int sum2=0;  sum2 is never used

   /* You can't make an array without telling it's size. rows and cols
   have not been assigned a value, yet.
   */
   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];
   //int rows_sum[rows]; //rows could be ANY value, still.

/* your program isn't designed for this
   printf("enter rows and cols [1..50] ==> ");
	scanf("%d %d",&rows,&cols);
*/

/* You can save yourself this code, just by making the array initialize to
zero's, when you declare it:
row_sum[4] = { 0 };
This only works when you first declare them, not at any later time
*/
 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);
                                                                                           //start of searching code
for (tndex =rows;tndex>0; tndex++)
	{
		for (lndex =cols; lndex>0; lndex++)
		{

            for (index =0;index<tndex; index++)
	              {
		                 for (kndex =0; kndex<lndex; kndex++)
		                     {

			                    sum2=sum2+matrix[index][kndex];
		                      }
	              }

          if (sum2==inp){
            counter++;
          }
		}
	}
	                       
	printf("%d",&counter);
	                                                                                  // end of searching code
   return 0;

}//end main

I built a code that does your algorithm using function i have build.
I think there is problem in the array input on the signatures
how input an array
i tried int* matrix[][]

??

Code:

#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);
	                           // end of searching code
   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;
}

i changed a code above
i think it shuld work
the problem is with tha array input in a function

Your search for sub domains == 8 is very similar to how a queen searches a chessboard, for it's possible moves.

Every matrix position will need to check in 8 directions: (using a clock for reference: 12, 1:30, 3, 4:30, 6, 7:30, 9, and 10:30 o'clock). That covers all rows, all columns, and all 4 diagonals, also.

Edit: Nope, I see you're not using the diagonals - but you are using any 4 sided shape that adds up to 8 (in this case), and that the square is a part of (and hasn't been previously named).

i tried to implement this algorithm

Originally Posted by C_ntua

For you given matrice

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

can you find the sub-matrices with an algorithm and not by hand?

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 built the code above for it
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 cant check if its the right one
because i cant input my array into the functions

Code:

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