比较C中的两个2 D数组

Question

我有比较两个2D阵列的问题。

例：

第一个数组： xxooo oxxoo oxooo oxooo OOOOO

第二个数组（可以旋转）： 0×00 XXXX xooo

但是当我比较它们时，我设法旋转并检查左侧顶部的相似性，有两个for循环，如下所示：

firstArr[i][j] == secArr[i][j]

如果尺寸大于第二个数组，如何检查整个第一个数组中的相似性？

另一个例子：

这是我的代码：

#include <stdio.h>

int main()
{
    int i, j, pr, ps, pn, r, s;
    int indx = 0, indy = 0, brx = 0, bry = 0;
    int nema = 0;

    scanf(" %d %d %d %d", &r, &s, &pr, &ps);

    char prtljaga[r][s];
    char opredmet[pr][ps], opt1[pr][ps], opt2[ps][pr], opt3[ps][pr];
    int temp[r][s];

    for(i = 0; i < r; i++){
        for(j = 0; j < s; j++){
            temp[i][j] = 0;
        }
    }

    for(i = 0; i < r; i++){
        for(j = 0; j < s; j++){
            scanf(" %c", &prtljaga[i][j]);
        }
    }

    scanf(" %d", &pn);

    while(pn != 0){
        for(i = 0; i < pr; i++){
            for(j = 0; j < ps; j++){
                scanf(" %c", &opredmet[i][j]);
            }
        }

        for(i = 0; i < pr; i++){
            for(j = 0; j < ps; j++){
                opt1[pr-1-i][j] = opredmet[i][j];
            }
        }

        for(i = 0; i < pr; i++){
            for(j = 0; j < ps; j++){
                opt2[j][pr-1-i] = opredmet[i][j];
            }
        }

        for(i = 0; i < pr; i++){
            for(j = 0; j < ps; j++){
                opt3[ps-1-j][i] = opredmet[i][j];
            }
        }

        /* while */
        for(i = 0; i < r; i++){
            for(j = 0; j < s; j++){
                if(j > pr){
                    break;
                }else{
                    if(prtljaga[i][j] == opredmet[i][j]){
                        temp[i][j] = 1;
                    }else{

                    }
                }
            }
        }

        indx = 0; indy = 0; brx = 0; bry = 0;
        for(i = 0; i < r; i++){
            for(j = 0; j < s; j++){
                if(temp[i][j] == 1){
                    brx++;
                    if(brx == 1){
                        indx = j;
                        indy = i;
                    }
                }else{
                    if(brx != pr){
                         brx = 0;
                    }
                }
            }

            if(brx == pr){
                bry++;

                if(bry != pr){
                     brx = 0;
                }
            }else{
                if(bry != ps){
                    bry = 0;
                }
            }

            if(brx == pr && bry == ps){
                printf("%d: [%d, %d]", pn, indx+1, indy+1);
                nema = 1;
                break;
            }
        }

        for(i = 0; i < r; i++){
            for(j = 0; j < s; j++){
                temp[i][j] = 0;
            }
        }
        /* while */

        /* while */
        for(i = 0; i < r; i++){
            for(j = 0; j < s; j++){
                if(j > pr){
                    break;
                }else{
                    if(prtljaga[i][j] == opt1[i][j]){
                        temp[i][j] = 1;
                    }else{

                    }
                }
            }
        }

        for(i = 0; i < r; i++){
            for(j = 0; j < s; j++){
                printf("%d", temp[i][j]);
            }
            printf("\n");
        }

        indx = 0; indy = 0; brx = 0; bry = 0;
        for(i = 0; i < r; i++){
            for(j = 0; j < s; j++){
                if(temp[i][j] == 1){
                    brx++;
                    if(brx == 1 && bry == 0){
                        indx = j;
                        indy = i;
                    }
                }else{
                    if(brx != pr){
                         brx = 0;
                    }
                }
            }

            if(brx == pr){
                bry++;

                if(bry != ps){
                    brx = 0;
                }
            }else{
               if(bry != ps){
                    bry = 0;
                }
            }

            if(brx == pr && bry == ps){
                printf("%d: [%d, %d]", pn, indx+1, indy+1);
                nema = 1;
                break;
            }
        }

        if(nema == 0){
            for(i = 0; i < r; i++){
                for(j = 0; j < s; j++){
                    temp[i][j] = 0;
                }
            }
        }

        for(i = 0; i < r; i++){
            for(j = 0; j < s; j++){
                temp[i][j] = 0;
            }
        }
        /* while */

        /* while */
        for(i = 0; i < r; i++){
            for(j = 0; j < s; j++){
                if(j > pr){
                    break;
                }else{
                    if(prtljaga[i][j] == opt2[i][j]){
                        temp[i][j] = 1;
                    }else{

                    }
                }
            }
        }

        indx = 0; indy = 0; brx = 0; bry = 0;
        for(i = 0; i < r; i++){
            for(j = 0; j < s; j++){
                if(temp[i][j] == 1){
                    brx++;
                    if(brx == 1 && bry == 0){
                        indx = j;
                        indy = i;
                    }
                }else{
                    if(brx != ps){
                         brx = 0;
                    }
                }
            }

            if(brx == ps){
                bry++;

                if(bry != pr){
                     brx = 0;
                }
            }else{
                if(bry != pr){
                    bry = 0;
                }
            }

            if(brx == ps && bry == pr){
                printf("%d: [%d, %d]", pn, indx+1, indy+1);
                nema = 1;
                break;
            }
        }

        for(i = 0; i < r; i++){
            for(j = 0; j < s; j++){
                temp[i][j] = 0;
            }
        }

        for(i = 0; i < r; i++){
            for(j = 0; j < s; j++){
                if(j > pr){
                    break;
                }else{
                    if(prtljaga[i][j] == opt3[i][j]){
                        temp[i][j] = 1;
                    }else{

                    }
                }
            }
        }

        indx = 0; indy = 0; brx = 0; bry = 0;
        for(i = 0; i < r; i++){
            for(j = 0; j < s; j++){
                if(temp[i][j] == 1){
                    brx++;
                    if(brx == 1 && bry == 0){
                        indx = j;
                        indy = i;
                    }
                }else{
                    if(brx != ps){
                         brx = 0;
                    }
                }
            }

            if(brx == ps){
                bry++;

                if(bry != pr){
                     brx = 0;
                }
            }else{
                if(bry != pr){
                    bry = 0;
                }
            }

            if(brx == ps && bry == pr){
                printf("%d: [%d, %d]", pn, indx+1, indy+1);
                nema = 1;
                break;
            }
        }

        for(i = 0; i < r; i++){
            for(j = 0; j < s; j++){
                temp[i][j] = 0;
            }
        }

        indx = 0, indy = 0, brx = 0, bry = 0; pn--;
    }

    if(nema == 0){
        printf("-1");
    }
    return 0;
}

Answer 1

我不打算进入已发布的非常大的程序，除了要注意您应该始终检查从返回有意义值的函数返回的值。 scanf()函数族返回有意义的值，应检查这些值以帮助验证输入是否符合预期。在发布的代码中，如果用户输入非数字输入（意外或故意），代码将继续使用不确定的值，就好像没有任何错误一样，从而导致潜在的未定义行为。

针对较小图案检查较大阵列的一种策略是将较小的感兴趣区域复制到与图案具有相同尺寸的临时阵列。可以使用memcmp()将此临时数组与模式进行比较。可以对临时阵列应用各种转换，然后可以再次针对该模式检查该转换。

这是一个使用问题帖子中的一些示例输入的示例程序。如果找到匹配，则contains_similar()函数返回1，找不到匹配的0。一些替代方案是返回第一个匹配模式的（左上）索引，或者将所有这些索引存储在数组中。有一个reverse_rows()函数作为示例转换。如果第一次比较无法匹配，则此变换将应用于contains_similar()中的临时数组，然后将变换后的区域再次与模式进行比较。更复杂的版本将使用指向变换函数的指针数组，这些指针可以在比较循环中迭代。

#include <stdio.h>
#include <string.h>

int contains_similar(size_t rows,
                     size_t cols,
                     char arr[rows][cols],
                     size_t prows,
                     size_t pcols,
                     char pat[prows][pcols]);

void reverse_rows(size_t rows, size_t cols, char arr[rows][cols]);
void print_array(size_t rows, size_t cols, char arr[rows][cols]);

int main(void)
{
    char array[][10] = {
        { 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o' },
        { 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o' },
        { 'o', 'o', 'x', 'o', 'o', 'o', 'x', 'o', 'o', 'o' },
        { 'o', 'o', 'x', 'x', 'x', 'x', 'x', 'o', 'o', 'x' },
        { 'o', 'x', 'x', 'o', 'o', 'o', 'o', 'o', 'o', 'x' },
        { 'o', 'x', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'x' },
        { 'o', 'x', 'x', 'o', 'x', 'x', 'o', 'o', 'o', 'x' },
        { 'o', 'o', 'x', 'o', 'x', 'o', 'o', 'o', 'x', 'x' },
        { 'o', 'x', 'x', 'o', 'x', 'o', 'o', 'o', 'o', 'o' },
        { 'o', 'o', 'o', 'o', 'x', 'x', 'x', 'x', 'x', 'o' }
    };

    char pattern[][5] = {
        { 'x', 'x', 'x', 'x', 'x' },
        { 'x', 'o', 'o', 'o', 'x' }
    };

    size_t arr_cols = sizeof array[0];
    size_t arr_rows = sizeof array / arr_cols;
    size_t pat_cols = sizeof pattern[0];
    size_t pat_rows = sizeof pattern / pat_cols;

    printf("Working with %zu X %zu array:\n", arr_rows, arr_cols);
    putchar('\n');
    print_array(arr_rows, arr_cols, array);

    putchar('\n');
    printf("Using %zu X %zu pattern:\n", pat_rows, pat_cols);
    putchar('\n');
    print_array(pat_rows, pat_cols, pattern);

    putchar('\n');
    printf("Similar pattern %s in array\n",
           contains_similar(arr_rows, arr_cols, array,
                            pat_rows, pat_cols, pattern)
           ? "found"
           : "not found");

    return 0;
}

int contains_similar(size_t rows,
                     size_t cols,
                     char arr[rows][cols],
                     size_t prows,
                     size_t pcols,
                     char pat[prows][pcols])
{
    char temp[prows][pcols];
    size_t last_row = rows - prows;
    size_t last_col = cols - pcols;
    size_t pat_sz = prows * pcols;

    /* i and j index the upper-left corner of the region of interest */
    for (size_t i = 0; i <= last_row; i++) {
        for (size_t j = 0; j <= last_col; j++) {

            /* Copy region of interest to temp[][] */
            for (size_t k = 0; k < prows; k++) {
                memcpy(temp[k], &arr[i+k][j], pcols);
            }

            /* Make comparisons with transformations */
            if (memcmp(temp, pat, pat_sz) == 0) {      // pattern matched
                return 1;
            }

            reverse_rows (prows, pcols, temp);
            if (memcmp(temp, pat, pat_sz) == 0) {      // pattern matched
                return 1;
            }
        }
    }

    return 0;                                          // no match found
}

void reverse_rows(size_t rows, size_t cols, char arr[rows][cols])
{
    char temp[cols];
    size_t swap_row = rows - 1;

    for (size_t i = 0; i < swap_row; i++) {
        memcpy(temp, arr[i], cols);
        memmove(arr[i], arr[swap_row], cols);
        memcpy(arr[swap_row], temp, cols);
        --swap_row;
    }
}

void print_array(size_t rows, size_t cols, char arr[rows][cols])
{
    for (size_t i = 0; i < rows; i++) {
        for (size_t j = 0; j < cols; j++) {
            putchar(arr[i][j]);
        }
        putchar('\n');
    }
}

节目输出：

Working with 10 X 10 array:

oooooooooo
oooooooooo
ooxoooxooo
ooxxxxxoox
oxxoooooox
oxooooooox
oxxoxxooox
ooxoxoooxx
oxxoxooooo
ooooxxxxxo

Using 2 X 5 pattern:

xxxxx
xooox

Similar pattern found in array

检查图案旋转

上面的代码适用于某些用途，但是在OP目标中检查较大模式中的旋转模式时，它将无法轻松工作。非方形图案将在旋转下改变形状，并且在旋转之前和之后将以不同的方式适合较大的图案。

可以重新配置上述代码以针对子模式检查较大的模式，然后针对旋转的子模式检查等等。在重新配置时，模式阵列可以包裹在结构中。这些结构可以包含大于预期模式的数组，并且还可以包含实际模式的大小。将图案尺寸与图案的表示保持在一起是方便的。较大的图案，子图案和感兴趣的区域都存储在这样的Pattern structs中。

memcmp()函数仍可用于比较模式，但现在比较整个超大数组。这可能不是最有效的比较方法。请注意，memcpy()不再用于复制感兴趣的区域，尽管它可能是;这里使用嵌套循环代替变种。

此版本还存储模式匹配的位置。 Matches struct包含一个足够大的Coordinate structs数组（ARR_SZ * ARR_SZ成员），如果模式中的每个位置都匹配，则保持匹配。当找到匹配时，匹配子模式的左上角的索引存储在数组中，并且数字匹配.num递增。

large模式是已发布的示例输入的修改版本，其中包含不同方向的一些模式匹配。在main()中，large和small模式被初始化，并且found结构被初始化为0。调用find_similar()函数;这个函数调用find_pattern()与small模式和这种模式的旋转。当find_similar()返回时，将打印一条消息以指示是否找到任何匹配项，如果是，则显示匹配模式的位置。

如果OP对此解决方案中使用structs不满意，那么可以找到这里介绍的两者之间令人满意的解决方案。

#include <stdio.h>
#include <string.h>

#define ARR_SZ  100

struct Pattern
{
    size_t nrows;
    size_t ncols;
    char arr[ARR_SZ][ARR_SZ];
};

struct Coordinate
{
    size_t row;
    size_t col;
};

struct Matches
{
    size_t num;
    struct Coordinate location[ARR_SZ * ARR_SZ];
};

int find_pattern(struct Pattern pat,
                 struct Pattern sub,
                 struct Matches *found);

int find_similar(struct Pattern pat,
                 struct Pattern sub,
                 struct Matches *found);

void print_pattern(struct Pattern pat);
struct Pattern rotate_pattern(struct Pattern pat);

int main(void)
{
    struct Pattern large = {
        .arr = {
            { 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o' },
            { 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o' },
            { 'o', 'o', 'x', 'o', 'o', 'o', 'x', 'o', 'o', 'o' },
            { 'o', 'x', 'x', 'x', 'x', 'x', 'x', 'o', 'x', 'x' },
            { 'o', 'x', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'x' },
            { 'o', 'x', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'x' },
            { 'o', 'x', 'o', 'o', 'x', 'x', 'o', 'o', 'o', 'x' },
            { 'o', 'x', 'x', 'o', 'x', 'o', 'o', 'o', 'x', 'x' },
            { 'o', 'x', 'x', 'o', 'x', 'o', 'o', 'o', 'x', 'o' },
            { 'o', 'o', 'o', 'o', 'x', 'x', 'x', 'x', 'x', 'o' }
        }
    };
    large.ncols = 10;
    large.nrows = 10;

    struct Pattern small = {
        .arr = {
            { 'x', 'x', 'x', 'x', 'x' },
            { 'x', 'o', 'o', 'o', 'x' }
        }
    };
    small.ncols = 5;
    small.nrows = 2;

    struct Matches found = { .num = 0 };

    printf("Working with %zu X %zu array:\n", large.nrows, large.ncols);
    putchar('\n');
    print_pattern(large);

    putchar('\n');
    printf("Using %zu X %zu pattern:\n", small.nrows, small.ncols);
    putchar('\n');
    print_pattern(small);

    int ret = find_similar(large, small, &found);
    putchar('\n');
    printf("Similar patterns %s in array\n", ret ? "found" : "not found");

    if (ret) {
        for (size_t i = 0; i < found.num; i++) {
            printf("[%zu, %zu]\n",
                   found.location[i].row,
                   found.location[i].col);
        }
    }

    return 0;
}

int find_pattern(struct Pattern pat,
                 struct Pattern sub,
                 struct Matches *found)
{
    static size_t max_found = sizeof found->location / sizeof *found->location;
    int ret = 0;

    size_t rows = pat.nrows;
    size_t cols = pat.ncols;
    size_t srows = sub.nrows;
    size_t scols = sub.ncols;
    size_t last_row = rows - srows;
    size_t last_col = cols - scols;

    struct Pattern roi = { .nrows = srows,
                           .ncols = scols,
                           .arr = { { 0 } } };

    /* i and j index the upper-left corner of the region of interest */
    for (size_t i = 0; i <= last_row; i++) {
        for (size_t j = 0; j <= last_col; j++) {

            /* Copy region of interest to roi */
            for (size_t k = 0; k < srows; k++) {
                for (size_t l = 0; l < scols; l++) {
                    roi.arr[k][l] = pat.arr[i + k][j + l];
                }
            }

            /* Make comparison */
            if (memcmp(roi.arr, sub.arr, sizeof roi.arr) == 0) {

                /* Store location of match */
                struct Coordinate *cdt = &found->location[found->num];
                cdt->row = i;
                cdt->col = j;
                found->num += 1;
                if (found->num > max_found) {
                    found->num = max_found;
                }
                ret = 1;
            }
        }
    }

    return ret;
}

int find_similar(struct Pattern pat,
                 struct Pattern sub,
                 struct Matches *found)
{
    int ret = find_pattern(pat, sub, found);
    struct Pattern rot = sub;
    for (int i = 0; i < 3; i++) {
        rot = rotate_pattern(rot);
        ret = find_pattern(pat, rot, found) || ret;
    }

    return ret;
}

void print_pattern(struct Pattern pat)
{
    size_t rows = pat.nrows;
    size_t cols = pat.ncols;

    for (size_t i = 0; i < rows; i++) {
        for (size_t j = 0; j < cols; j++) {
            putchar(pat.arr[i][j]);
        }
        putchar('\n');
    }
}

struct Pattern rotate_pattern(struct Pattern pat)
{
    size_t rows = pat.nrows;
    size_t cols = pat.ncols;

    struct Pattern rotated = { .nrows = cols, .ncols = rows };
    for (size_t i = 0; i < rows; i++) {
        for (size_t j = 0; j < cols; j++) {
            rotated.arr[j][rows - i - 1] = pat.arr[i][j];
        }
    }

    return rotated;
}

节目输出：

Working with 10 X 10 array:

oooooooooo
oooooooooo
ooxoooxooo
oxxxxxxoxx
oxooooooox
oxooooooox
oxooxxooox
oxxoxoooxx
oxxoxoooxo
ooooxxxxxo

Using 2 X 5 pattern:

xxxxx
xooox

Similar patterns found in array
[3, 8]
[2, 2]
[8, 4]
[3, 1]

Answer 2

我现在能想到的是通过同时遍历越来越大的阵列并检查相似性来使用Two Pointers技术。

您仍然需要对其进行一些增强，以便能够检查彼此相同的行。