Two-dimensional Arrays (matrices) in C

Question

I'm writing code that checks if m2 matrix is a sub-matrix of m1.

Currently I have created a method that receives matrix m1 and matrix m2 of fixed size. First of all I check that m1 is larger than m2 otherwise m2 cannot be a sub-matrix of m1. Then I have the variable result which indicates 1 if m2 is sub-matrix, or indicates 0 if it is not.

I can't find the right technique to check this thing out. I have started scanning the rows and columns of the arrays, but I don't know how to correctly structure the code to verify it correctly.

This is the code:

void CheckSubMatrix (int rows, int cols, int m1[][cols], int m2[2][2]){
     int rowsm2=2;
     int colsm2=2;
     int result=1;
     
     if(rows >= rowsm2 && cols >= colsm2){
              for(int i=0; i<rows; i++){
                       for(int j=0; j<cols; j++){
                                if(m1[i][j] != m2[i][j]
                                         result=0;
                       }
              }
     } else {
     result = 0;


     if (result)
     printf("Is a Sub-Matrix");
     else
     printf("Is not a Sub-Matrix");

I'm a beginner and I'm trying to understand how two-dimensional arrays and matrices work in order to understand even the simplest one-dimensional arrays.

Thanks to those who will help me.

Note:

• example of sub-matrix: image

EDIT: I know that the code if(m1[i][j] != m2[i][j] result=0; doesn't work, because the program will take the values of i and j at the last for loop. But I just didn't know how to be able to implement it.

Answer 1

Making judicious use of functions makes the code easier, I think. Using VLA notation for all array arguments means that the code can handle your three test cases, plus a couple of extras with non-square matrices. (The use of void CheckSubMatrix (int rows, int cols, int m1[][cols], int m2[2][2]){ in the code in the question prevents any of the sample tests from working; that checking function only accepts 2x2 sub-matrices). Since the code is only checking the matrices, the matrices should be specified with the const qualifier.

#include <stdio.h>
#include <assert.h>

static int SubMatrixHere(int r, int c,
                         int rows1, int cols1, const int m1[rows1][cols1],
                         int rows2, int cols2, const int m2[rows2][cols2])
{
    assert(r + rows2 <= rows1 && c + cols2 <= cols1);
    for (int i = 0; i < rows2; i++)
    {
        for (int j = 0; j < cols2; j++)
        {
            if (m1[r+i][c+j] != m2[i][j])
                return 0;
        }
    }
    return 1;
}

static int CheckSubMatrix(int rows1, int cols1, const int m1[rows1][cols1],
                          int rows2, int cols2, const int m2[rows2][cols2])
{
    if (rows1 < rows2 || cols1 < cols2)
        return 0;

    int ub_rows = rows1 - rows2 + 1;
    int ub_cols = cols1 - cols2 + 1;
    for (int i = 0; i < ub_rows; i++)
    {
        for (int j = 0; j < ub_cols; j++)
        {
            /* The test for m1[i][j] == m2[0][0] is a big saving */
            if (m1[i][j] == m2[0][0] &&
                SubMatrixHere(i, j, rows1, cols1, m1, rows2, cols2, m2))
                return 1;
        }
    }
    return 0;
}

static void dump_matrix(const char *tag, int rows, int cols, const int matrix[rows][cols])
{
    printf("%s (%dx%d):\n", tag, rows, cols);
    for (int i = 0; i < rows; i++)
    {
        const char *pad = "";
        int length = 0;
        for (int j = 0; j < cols; j++)
        {
            length += printf("%s%d", pad, matrix[i][j]);
            if (length > 60)
            {
                putchar('\n');
                length = 0;
                pad = "";
            }
            else
                pad = ", ";
        }
        if (length > 0)
            putchar('\n');
    }
    putchar('\n');
}

static void test_submatrix(const char *t1, int r1, int c1, const int m1[r1][c1],
                           const char *t2, int r2, int c2, const int m2[r2][c2])
{
    dump_matrix(t1, r1, c1, m1);
    dump_matrix(t2, r2, c2, m2);
    if (CheckSubMatrix(r1, c1, m1, r2, c2, m2))
        printf("%s is a sub-matrix of %s\n", t2, t1);
    else
        printf("%s is not a sub-matrix of %s\n", t2, t1);
    putchar('\n');
}

int main(void)
{
    int m1[4][4] =
    {
        { 1, 4, 6, 8 },
        { 2, 5, 7, 0 },
        { 3, 6, 9, 0 },
        { 4, 5, 8, 1 },
    };
    int m2[3][3] =
    {
        { 1, 4, 6 },
        { 2, 5, 7 },
        { 3, 6, 9 },
    };
    int m3[3][3] =
    {
        { 5, 7, 0 },
        { 6, 9, 0 },
        { 5, 8, 1 },
    };
    int m4[3][3] =
    {
        { 1, 4, 6 },
        { 2, 5, 7 },
        { 3, 6, 2 },
    };

    test_submatrix("m1", 4, 4, m1, "m2", 3, 3, m2);
    test_submatrix("m1", 4, 4, m1, "m3", 3, 3, m3);
    test_submatrix("m1", 4, 4, m1, "m4", 3, 3, m4);

    const int m5[6][4] =
    {
        { 68, 59, 61, 70 },
        { 65, 86, 44,  9 },
        { 23, 55, 24, 31 },
        { 51, 21, 10, 99 },
        { 19, 99, 43, 95 },
        { 64, 25, 79, 67 },
    };

    const int m6[2][3] =
    {
        { 55, 24, 31 },
        { 21, 10, 99 },
    };

    const int m7[4][2] =
    {
        { 44,  9 },
        { 24, 31 },
        { 10, 99 },
        { 43, 96 },
    };
    test_submatrix("m5", 6, 4, m5, "m6", 2, 3, m6);
    test_submatrix("m5", 6, 4, m5, "m7", 4, 2, m7);

    return 0;
}

Output:

m1 (4x4):
1, 4, 6, 8
2, 5, 7, 0
3, 6, 9, 0
4, 5, 8, 1

m2 (3x3):
1, 4, 6
2, 5, 7
3, 6, 9

m2 is a sub-matrix of m1

m1 (4x4):
1, 4, 6, 8
2, 5, 7, 0
3, 6, 9, 0
4, 5, 8, 1

m3 (3x3):
5, 7, 0
6, 9, 0
5, 8, 1

m3 is a sub-matrix of m1

m1 (4x4):
1, 4, 6, 8
2, 5, 7, 0
3, 6, 9, 0
4, 5, 8, 1

m4 (3x3):
1, 4, 6
2, 5, 7
3, 6, 2

m4 is not a sub-matrix of m1

m5 (6x4):
68, 59, 61, 70
65, 86, 44, 9
23, 55, 24, 31
51, 21, 10, 99
19, 99, 43, 95
64, 25, 79, 67

m6 (2x3):
55, 24, 31
21, 10, 99

m6 is a sub-matrix of m5

m5 (6x4):
68, 59, 61, 70
65, 86, 44, 9
23, 55, 24, 31
51, 21, 10, 99
19, 99, 43, 95
64, 25, 79, 67

m7 (4x2):
44, 9
24, 31
10, 99
43, 96

m7 is not a sub-matrix of m5

Answer 2

1. Use the correct types for sizes (size_t)
2. You need more loops

int issubmatrix(size_t hrows, size_t hcols, int (*haystack)[hcols],
                size_t nrows, size_t ncols, int (*needle)[ncols])
{
    int itis = 0;
    int exitloop = 0;

    if(haystack && needle && ncols <= hcols && nrows <= hrows)
    {
        for(size_t start_row = 0; start_row <= hrows - nrows; start_row++)
        {
            for(size_t start_col = 0; start_col <= hcols - ncols; start_col++)
            {
                exitloop = 0;
                for(size_t row = 0; row < nrows; row++)
                {
                    for(size_t col = 0; col < ncols; col++)
                    {
                        if(haystack[start_row + row][start_col + col] != needle[row][col])
                        {
                            exitloop = 1;
                            break;
                        }
                        if(exitloop) break;
                    }
                    if(exitloop) break;
                }
                if(!exitloop) itis = 1;
            }
            if(itis) break;
        }
    }
    return itis;
}


int main(void)
{
    int haystack[][4] = {
        {1,4,6,8},
        {2,5,7,0},
        {3,6,9,0},
        {4,5,8,1},
    };
    int needle1[][3] =
    {
        {1,4,6},
        {2,5,7},
        {3,6,9},
    };

    int needle2[][3] =
    {
        {5,7,0},
        {6,9,0},
        {5,8,1},
    };

    int needle3[][3] =
    {
        {1,4,6},
        {2,5,7},
        {3,6,2},
    };

    printf("%d\n", issubmatrix(4,4, haystack, 3,3, needle1));
    printf("%d\n", issubmatrix(4,4, haystack, 3,3, needle2));
    printf("%d\n", issubmatrix(4,4, haystack, 3,3, needle3));
}

https://godbolt.org/z/YTMfWP8ca