Почему код не выходит из рекурсии?

Question

Проблема состоит в том, чтобы найти количество раз, когда слово встречается в данной N x N матрице алфавитов. Мы можем перейти из любой ячейки в другую соседнюю ячейку. В первой строке записано одно целое число N, а затем матрица N x N. Следующая строка имеет M (размер слова), а затем строку, которая будет найдена в матрице.

Input:
4
ABCD
ABCD
ABCD
ABCD
2
BC

Expected output:
10

Я написал следующий код для того же и использовал рекурсию для решения проблемы. Функция adj проверяет, является ли символ смежным в матрице с предыдущим символом, используя их индексы. Функция check увеличивает счетчик всякий раз, когда строка завершается. 2-й массив хранит проверку посещенных и не посещенных элементов.

Я получаю вывод как

OUPUT
1

РЕДАКТИРОВАТЬ 1: Этот вывод только из-за оператора отладочной печати,поэтому оператор if посещается только один раз. Это не означает, что переменная count равна 1 после многих рекурсивных вызовов.

РЕДАКТИРОВАТЬ 2: Не должно быть & в выражении scanf для слова. Но все же вывод не желаемый.

РЕДАКТИРОВАТЬ 3:

Another input
7
SHELDON
HSTYUPQ 
EHGXBAJ
LMNNQQI
DTYUIOP
OZXCVBN
NQWERTY
7
SHELDON

Expected output:
5

My output - 1

РЕДАКТИРОВАТЬ 4 (решено!): Таким образом, проблема была в написании нет. столбцов как 500 для матрицы сетки, изменение его на 5 сделало свою работу! Благодаря @ gsamaras

Код

#include <stdio.h>

int vis[500][500], count;

int adj(int a, int b, int c, int d) {
    if((c == a - 1) && (d == b - 1)) {
        return 1;
    }
    else if((c == a - 1) && (d == b)) {
        return 1;
    }
    else if((c == a) && (d == b - 1)) {
        return 1;
    }
    else if((c == a - 1) && (d == b + 1)) {
        return 1;
    }
    else if((c == a + 1) && (d == b)) {
        return 1;
    }
    else if((c == a + 1) && (d == b + 1)) {
        return 1;
    }
    else if((c == a) && (d == b + 1)) {
        return 1;
    }
    else if((c == a + 1) && (d == b - 1)) {
        return 1;
    }
    else {
        return 0;
    }

}

void check(char grid[][500],int i, int j, int id, char word[], int n, int m) {
    if(id == m) {
        count++;
        printf("%d\n", count); // just to debug
    }
    else {
        for(int p = 0; p < n; p++) {
            for(int q = 0;q < n; q++) {
                if((grid[p][q] == word[id]) && (adj(i, j, p, q)) && (vis[p][q] != 1)) {
                    vis[p][q] = 1;
                    check(grid, p, q, id + 1, word, n, m);
                    vis[p][q] = 0;
                }
            }
        }
    }
}

int main() {
    int n, m, id = 0;
    char blank;
    scanf("%d", &n);
    scanf("%c", &blank);
    char grid[n][n+1];
    for(int i = 0; i < n; i++) {
        scanf("%s", grid[i]);
        grid[i][n] = '\0';
    }
    scanf("%d", &m);
    char word[m+1];
    scanf("%s", &word);

    for(int i = 0; i < n; i++) {
        for(int j = 0;j < n; j++) {
            if(grid[i][j] == word[id]) {
                vis[i][j] = 1;
                check(grid, i, j, id + 1, word, n, m);
                vis[i][j] = 0;
            }
        }
    }
    printf("%d\n", count);
    return 0;
}

Answer 1

Измените это:

void check(char grid[][500], ......

на это:

void check(char grid[][5], .......   // that should be equal to N + 1 (5 in your case)

, поскольку ваша сетка имеет размер N x N + 1. С размером 500 в качестве измерения вы исказилисетка, и при попытке рекурсивного поиска в ней вы не будете пересекать сетку, которую вы ожидаете пересечь ..

Как видите, она не гибкая, поскольку N может варьироваться. Вы не можете объявить grid глобальным, поскольку его размеры не являются фиксированными. Вместо этого следует использовать динамическое выделение памяти .

---

Измените это:

scanf("%s", &word);

на это:

scanf("%s", word);

, начиная с word представляет собой массив символов.

---

Полный пример с динамическим распределением памяти:

#include <stdio.h>
#include <stdlib.h>

int vis[500][500], count;

char **get(int N, int M) { /* Allocate the array */
    int i;
    char **p;
    p = malloc(N*sizeof(char *));
    for(i = 0 ; i < N ; i++)
        p[i] = malloc( M*sizeof(char) );
    return p;
}

void free2Darray(char** p, int N) {
    int i;
    for(i = 0 ; i < N ; i++)
        free(p[i]);
    free(p);
}

int adj(int a, int b, int c, int d) {
    // Same as in your question
}

void check(char** grid, int i, int j, int id, char word[], int n, int m) {
    if(id == m) {
        count++;
        printf("count = %d\n", count); // just to debug
    }
    else {
        for(int p = 0; p < n; p++) {
            for(int q = 0;q < 499; q++) {
              //printf("p = %d, q = %d, id = %d, grid[p][q] = %c, word[id] = %c\n", p, q, id, grid[p][q], word[id]);
                if((grid[p][q] == word[id]) && (adj(i, j, p, q)) && (vis[p][q] != 1)) {
                    vis[p][q] = 1;
                    check(grid, p, q, id + 1, word, n, m);
                    vis[p][q] = 0;
                }
            }
        }
    }
}

int main() {
    int n, m, id = 0;
    char blank;
    scanf("%d", &n);
    scanf("%c", &blank);
    char** grid = get(n, n + 1);
    for(int i = 0; i < n; i++) {
        scanf("%s", grid[i]);
        grid[i][n] = '\0';
    }
    scanf("%d", &m);
    char word[m+1];
    scanf("%s", word);

    for(int i = 0; i < n; i++) {
        for(int j = 0;j < n; j++) {
            //printf("i = %d, j = %d, id = %d\n", i, j, id);
            if(grid[i][j] == word[id]) {
                vis[i][j] = 1;
                check(grid, i, j, id + 1, word, n, m);
                vis[i][j] = 0;
            }
        }
    }
    printf("%d\n", count);

    free2Darray(grid, n);
    return 0;
}

Вывод (для вашего 1-го ввода):

count = 1
count = 2
count = 3
count = 4
count = 5
count = 6
count = 7
count = 8
count = 9
count = 10
10

---

PS: не проблема, просто предложение о читабельности: count инициализируется в 0, потому что это глобальная переменная , но всегда лучше явно инициализировать ваши переменные, когда это важно.