1

The problem is to find the number of times a word occurs in a given N x N matrix of alphabets. We can move from any cell to other adjacent cell. The first line has one integer N and then a N x N matrix. Next line has M (size of the word) and then a string to be found in the matrix. 

Input:
4
ABCD
ABCD
ABCD
ABCD
2
BC

Expected output:
10

I have written the following code for the same and used recursion for solving the problem. The function adj checks if the character is adjacent in the matrix with the previous character using their indexes. The function check increases the count whenever the string is completed. The 2-d array keeps a check on the visited and unvisited elements.

I am getting the output as 

OUPUT
1

EDIT 1: This output is just because of the debugging print statement, so the if statement is being visited only once. It does not mean that the count variable is 1 after many recursion calls.

EDIT 2: There shouldn't be & in the scanf statement for word. But still the output is not the desired one.

EDIT 3: 

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

Expected output:
5

My output - 1

EDIT 4(Solved!): So the problem was in writing the no. of columns as 500 for the grid matrix, changing it to 5 did the job! Thanks to @gsamaras

Code

#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;
}
gsamaras
  • 71,951
  • 46
  • 188
  • 305
Sukrit Kapil
  • 35
  • 5

1 Answers1

2

Change this:

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

to this:

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

since your grid is of size N x N + 1. With the 500 as the dimension, you distorted the grid, and when trying to search into it recursively, you wouldn't traverse the grid that you would expect to traverse..

As you see this is not flexible, since N can vary. You cannot declare grid as global, since its dimensions are not fixed. Dynamic memory allocation should be used instead.

Change this:

scanf("%s", &word);

to this:

scanf("%s", word);

since word is an array of characters.

Complete example with Dynamic Memory Allocation:

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

Output (for your 1st input):

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

PS: Not a problem, just a suggestion about readability: count is initialized to 0, because it's a global variable, but it's always best to explicitly initialize your variables, when it matters.

gsamaras
  • 71,951
  • 46
  • 188
  • 305
  • Oops! Corrected this (not in the original question), now the output is 1 2 2 all numbers in next lines. So still not working – Sukrit Kapil Oct 20 '19 at 13:34
  • thanks for your concern. Oh yeah! corrected this one too, (since the last index would be m-1 not m), now the count is going upto 4 :). But I thought this code would cover up the diagonal case too.. – Sukrit Kapil Oct 20 '19 at 13:48
  • @SukritKapil I was wrong, it should be `m`. I found the issue, check the updated answer, which has a solution now! :D – gsamaras Oct 20 '19 at 13:51
  • But the problem is that n can be variable, like in the case of the second input I have added, so how to cope up with that. Actually N <= 500. So it can be variable. – Sukrit Kapil Oct 20 '19 at 13:57
  • Yeah I know what you mean. Have you learnt about dynamic memory allocation @SukritKapil? – gsamaras Oct 20 '19 at 14:00
  • Yeah, using malloc? – Sukrit Kapil Oct 20 '19 at 14:02
  • @gsamaras, what is meant by distorting the grid? In the above code, we are never traversing the grid beyond the value of n. So, even if the size is 500, only values of NxN will be considered as per in the loops. – Bhawan Oct 20 '19 at 14:03
  • 1
    Exactly @SukritKapil! I will update my answer now.. I was trying your second input (now that you fixed it), the code produces the correct result! :) – gsamaras Oct 20 '19 at 14:03
  • 1
    @Bhawan in the body of the function, a different `grid` is seen, one of 500 as the 2nd dimension, instead of `N + 1`. As a result, when you try to traverse it, you will see that it's empty (garbage values to be exact) in many cells, because all the grid is now treated as the first row of a grid with 500 columns. Change `n` in the second for loop to 499 to see what I mean. :) – gsamaras Oct 20 '19 at 14:06