检查C中随机字符矩阵中是否存在单词

Question

我目前正在使用 C 语言创建文字 search/boggle 游戏。玩家将在其上输入一个单词，程序将检查输入的单词是否存在于随机字符的二维矩阵中。我在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

数组索引问题。检查此代码

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

Answer 2

代码中存在多个问题：

true和false的定义不正确：你应该这样写：
```
typedef enum { false, true } bool;
```
您没有删除 fgets() 留在缓冲区中的尾随换行符。程序找不到单词，因为换行符不存在于矩阵中。使用以下命令删除此字符：
```
word[strcspn(word, "\n")] = '[=11=]';
```
测试 j > strlen(matrix[0]) - 1 不正确：您应该只测试 j >= SIZE 以验证坐标是否在矩阵内。
adjacentSearch() 应该 return 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] == '[=12=]')
        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")] = '[=12=]';
        if (exist(matrix, word)) {
            printf("Found\n");
        } else {
            printf("Not Found\n");
        }
    }
    return 0;
}

检查C中随机字符矩阵中是否存在单词

Check if word exists in the matrix of random characters in C

c

multidimensional-array

wordsearch

boggle