Проверьте, существует ли слово в матрице случайных символов в C

Question

В настоящее время я работаю над созданием словесной игры на языке C. На котором игрок будет вводить слово, и программа проверит, существует ли введенное слово в двумерной матрице случайных символов. У меня трудности с C языком. Может кто-нибудь помочь, если я делаю правильно? Или мне нужно изменить свои коды. Помощь очень ценится.

Так вот весь мой код. Когда я пытаюсь угадать это, всегда печатаю Not Found, хотя слово - это двумерная матрица случайного символа. Итак, мне нужна помощь с тем, что не так? И какой правильный код, чтобы проверить, существует ли слово?

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h>
#include <ctype.h>

#define SIZE 6 
#define MAX 10

typedef enum { true, false } bool;

// Draw the board with random characters
void board(char matrix[SIZE][SIZE]) {
    int i, j;
    for (i = 0; i < SIZE; i++) {
        for (j = 0; j < SIZE; j++) {
            matrix[i][j] = 'A' + rand() % ('Z' - 'A' + 1);
        }
    }
}

// Prints the board
void printBoard(char matrix[SIZE][SIZE]) {
    int i, j;
    srand((unsigned int)time(NULL));
    board(matrix);

    for (i = 0; i < SIZE; i++) {
        for (j = 0; j < SIZE; j++) {
            printf(" %c ", matrix[i][j]);
        }
        printf("\n");       
    }
}

bool adjacentSearch(char matrix[SIZE][SIZE], char *find, int i, int j, int index) {
    if (index == strlen(find))
        return true;

    if (i < 0 || j < 0 || i > SIZE - 1 || j > strlen(matrix[0]) - 1) {
        return true;
    }

    if (matrix[i][j] != find[index]) {
        return false;
    }

    matrix[i][j] = '*';

    bool searchFurther = adjacentSearch(matrix, find, i + 1, j, index + 1) ||
                         adjacentSearch(matrix, find, i - 1, j, index + 1) ||
                         adjacentSearch(matrix, find, i, j - 1, index + 1) ||
                         adjacentSearch(matrix, find, i, j + 1, index + 1);

    matrix[i][j] = find[index];
    return searchFurther;
}

bool exist(char matrix[SIZE][SIZE], char *find, int r, int c) {
    int len = strlen(find);

    if (len > r * c)
        return false;

    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < strlen(matrix[0]); j++) {
            if (matrix[i][j] == find[0]) {
                if (adjacentSearch(matrix, find, i, j, 0)) {
                    return true;
                }
            }
        }
    }
    return false;
}

// Driver 
int main() {
    char matrix[SIZE][SIZE];
    char word[MAX];

    printBoard(matrix);

    printf("\nThink of a word> ");
    fgets(word, MAX, stdin);
    //printf("word: %s", word);

    if (exist(matrix, word, SIZE, SIZE)) {
        printf("Found\n");
    } else {
        printf("Not Found\n");
    }
    return 0;
}

Answer 1

В коде есть несколько проблем:

• определение true и false неверно: вы должны написать:

  typedef enum { false, true } bool;
  

• вы не удаляете завершающий символ новой строки, оставленный в буфере, на fgets(). Программа не может найти слово, потому что символ новой строки отсутствует в матрице. Удалите этот символ с помощью:

  word[strcspn(word, "\n")] = '\0';
  

• тесты j > strlen(matrix[0]) - 1 неверны: вам нужно просто проверить, если j >= SIZE, чтобы убедиться, что координаты находятся внутри матрицы.

• adjacentSearch() должен возвращать false, когда i или j находятся за пределами матрицы.

Вот исправленная версия:

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

#define SIZE 6
#define MAX 40

typedef enum { false, true } bool;

// Draw the board with random characters
void board(char matrix[SIZE][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            matrix[i][j] = 'A' + rand() % ('Z' - 'A' + 1);
        }
    }
}

// Prints the board
void printBoard(char matrix[SIZE][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf(" %c ", matrix[i][j]);
        }
        printf("\n");
    }
}

bool adjacentSearch(char matrix[SIZE][SIZE], const char *find, int i, int j, int index) {
    if (find[index] == '\0')
        return true;

    if (i < 0 || j < 0 || i >= SIZE || j >= SIZE || matrix[i][j] != find[index])
        return false;

    matrix[i][j] = '*';
    bool found = (adjacentSearch(matrix, find, i + 1, j, index + 1) ||
                  adjacentSearch(matrix, find, i - 1, j, index + 1) ||
                  adjacentSearch(matrix, find, i, j - 1, index + 1) ||
                  adjacentSearch(matrix, find, i, j + 1, index + 1));
    matrix[i][j] = find[index];
    return found;
}

bool exist(char matrix[SIZE][SIZE], const char *find) {
    int len = strlen(find);
    if (len > SIZE * SIZE)
        return false;
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (adjacentSearch(matrix, find, i, j, 0)) {
                return true;
            }
        }
    }
    return false;
}

// Driver
int main() {
    char matrix[SIZE][SIZE], word[MAX];

    srand((unsigned int)time(NULL));
    board(matrix);
    printBoard(matrix);

    for (;;) {
        printf("\nThink of a word> ");
        if (!fgets(word, sizeof word, stdin))
            break;
        word[strcspn(word, "\n")] = '\0';
        if (exist(matrix, word)) {
            printf("Found\n");
        } else {
            printf("Not Found\n");
        }
    }
    return 0;
}

Answer 2

Проблема индексации массива. Проверьте этот код

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

#define SIZE 6
#define MAX 10

// typedef enum {true, false} bool;

// Draw the board with random characters
void board(char* matrix){
    int i, j;
    for(i=0; i<SIZE; i++){
            for(j=0; j<SIZE; j++){
                matrix[i*SIZE + j] = 'A'+(50 *i *j)%('Z'-'A'+1);
        }
    }
}

// Prints the board
void printBoard(char* matrix){
    int i, j;
    srand((unsigned int)time(NULL));
    board(matrix);

    for(i=0; i<SIZE; i++){
            for(j=0; j<SIZE; j++){
                    printf(" %c ", matrix[i*SIZE + j]);
            }
        printf("\n");
    }
}

enum class Direction : int
{
    Left = 0,
    Right,
    Up,
    Down,
    Unknown
};

bool SearchGivenStart(char* matrix,
char* find, int length,
int startRowIndex,
int startColumnIndex,
Direction direction)
{
     printf("Start %d %d\n", startRowIndex, startColumnIndex);
    int nextRowIndex = startRowIndex;
    int nextColumnIndex = startColumnIndex;
    for(int i = 1; i< length - 1 ;i++)
    {
        if(direction == Direction::Left)
        {
            nextColumnIndex -= 1;
        }
        else if (direction == Direction::Right)
        {
            nextColumnIndex += 1;
        }
        else if (direction == Direction::Up)
        {
            nextRowIndex -= 1;
        }
        else if (direction == Direction::Down)
        {
            nextRowIndex += 1;
        }
        else
        {
            // Assert error
        }

         printf("Next %d %d\n", nextRowIndex, nextColumnIndex);
        // Check bounds
        if(nextRowIndex  < 0 ||
        nextRowIndex > SIZE  ||
        nextColumnIndex  < 0 ||
        nextColumnIndex > SIZE )
        {
            printf("returning false out of bound\n");
            return false;
        }

        if (matrix [nextRowIndex * SIZE + nextColumnIndex] != find [i])
        {
            printf("returning false\n");
            return false;
        }

    }

    printf("returning true\n");
    return true;
}

bool Search(char* matrix, char* find, int length)
{
    // Find start
    // For each start candidate, serach all possible direction

    printf("%s %d\n", find, length);
    bool found = false;
    for (int i = 0; i < SIZE; i++)
    {
        for(int j= 0; j< SIZE; j++)
        {
            if ( matrix[i*SIZE + j] == find[0] )
                {
                    printf("%d %d\n", i, j);
                     found = SearchGivenStart(matrix,
                     find,
                     length,
                     i,
                     j,
                     Direction::Left);
                     if (found)
                        return true;

                     found = SearchGivenStart(matrix,
                     find,
                     length,
                     i,
                     j,
                     Direction::Right);
                     if (found)
                        return true;
                     found = SearchGivenStart(matrix,
                     find,
                     length,
                     i,
                     j,
                     Direction::Up);
                     if (found)
                        return true;
                     found = SearchGivenStart(matrix,
                     find,
                     length,
                     i,
                     j,
                     Direction::Down);
                     if (found)
                        return true;
                }
        }
    }
    return found;
}

bool adjacentSearch(char* matrix, char* find, int i, int j, int index){
    if(index == strlen(find))
        return true;

    if(i < 0 || j < 0 || i > SIZE-1 || j > SIZE - 1){
        return true;
    }

    if(matrix[i *SIZE + j] != find[index]){
        return false;
    }

    matrix[i*SIZE + j] = '*';

    bool searchFurther = adjacentSearch(matrix, find, i+1, j, index+1) || adjacentSearch(matrix, find, i-1, j, index+1) || adjacentSearch(matrix, find, i, j-1, index+1) || adjacentSearch(matrix, find, i, j+1, index+1);

    matrix[i * SIZE + j] = find[index];
    return searchFurther;
}

bool exist(char* matrix, char* find, int r, int c){
    int len = strlen(find);

    if(len > r * c)
        return false;

    for(int i=0; i<SIZE; i++){
        for(int j=0; j<SIZE; j++){
            if(matrix[i*SIZE + j] == find[0]){
                if(adjacentSearch(matrix, find, i, j, 0)){
                    return true;
                }
            }
        }
    }
    return false;
}


// Driver
int main(){
    char matrix[SIZE][SIZE];
    char word[MAX] = "SOKK";

    printBoard((char *)matrix);

    printf("\nThink of a word> ");
    fgets(word, MAX, stdin);
    printf("word: %s", word);

   /*if(exist((char *)matrix, word, SIZE, SIZE)){
        printf("Found\n");
   }*/
   if(Search((char *)matrix, word, strlen(word)))
      {
          printf("%s Found\n", word);
      }
    /*if(found)
    {
        printf("%s Found\n", word);
    }*/
    else{
        printf("%s Not Found\n", word);
    }
    return 0;
}