top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Find a matrix within another matrix?

+2 votes
650 views

Given bigger NxN matrix and a smaller MxM matrix print TRUE if the smaller matrix can be found in the bigger matrix else print FALSE

posted Jul 22, 2016 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes
void isSmallInBig()
{
    const int n = 4;
    int big[n][n] = { {11,12,13,14}, {21,22,23,24}, {31,32,33,34}, {41,42,43,44} };

    const int m = 3;
    int small[m][m] = { {21,22,23}, {31,32,33}, {41,42,43} };

    bool matchFound = false;
    bool flag = true;

    for(int r=0; r<n-m+1; r++)
    {
        for(int c=0; c<n-m+1; c++)
        {
            flag = true;
            for(int temp_r=0; temp_r<m; temp_r++)
            {
                for(int temp_c=0; temp_c<m; temp_c++)
                {
                    if(big[r + temp_r][c + temp_c] != small[temp_r][temp_c])
                    {
                        flag = false;
                        break;
                    }
                }
                if(flag==false) break;
            }
            if(flag==true) 
            {
                matchFound = true;
                break;
            }
        }
        if(flag==true) break;
    }

    if( matchFound )
        cout<<"Match found";
    else
        cout<<"Match not found";

}
answer Sep 23, 2016 by Manikandan J
Similar Questions
0 votes

suppose

A(n,m) = 
1 2 3         
4 5 6                            
7 8 9

and 

B(p, q) = 
1 1
1 1

What is best method to find min of square of difference of sub-matrices of A and B e.g.

sub-matrices of A =

1 2    |     2 3   |    4 5    |   5 6
3 4    |     5 6   |    7 8    |   8 9

Difference of first sub-matrix of A with B =

(1-1)  (2-1)    = |     0 1
(3-1)  (4-1)      |     2 3

sum of square of elements = 0*0 + 1*1 + 2*2 + 3*3 = 14

similar steps for other sub-matrices of A

Please suggest looking for an alternate method or algorithm which has time complexity less than O(n*m*p*q)

+7 votes

You have a 2D matrix. Only two ZEROs in matrix.
Find the path from 1st zero to 2nd zero with least sum.

1       6       8       9       0       3

4       9       -5      5       11      13

8       9       44      23      15      -20

7       9       7       -13     14      11      

0       16      23      31      16      7

67      5       4       23      21      19

Answer

1       6       8       9       0  ----> 3
                                         |
4       9       -5      5       11      13
                                         |
8       9       44      23      15      -20
                                         |
7 <---- 9 <---- 7 <--- -13 <--- 14 <---  11     
|
0       16      23      31      16        7

67      5       4       23      21       19
+2 votes

Problem
Given a table of size n * m, with each cell having a color value from the set {r, g, b}, find the area of the largest triangle that has one side parallel with the y – axis (vertical) and has no two vertices that have the same color value.

Input
First line contains the size of the matrix i.e. n * m where n is the number of rows and m is the number of columns.
n lines follow each having a string of size m.

Output
A single value for the area of the triangle.

Provide the C Code for the above problem?

+6 votes

Given a matrix with 1s and 0s, please find the number of groups of 1s. A group is defined by horizontally or vertically adjacent 1s.

...