在字符矩阵中搜索特定单词 [英] Searching a particular word in a matrix of characters

问题描述

我试图通过 C 在字符矩阵中搜索特定单词，但是无法找到固定的解决方案.

I was trying to search for a particular word in a matrix of characters through C but was unable to come to a fixed solution.

例如: 假设我必须在字符矩阵(3 * 9)中搜索单词 INTELLIGENT (一旦您从矩阵中选取了一个字符以构成一个句子，就无法再次选择它来构成相同的句子.从任何单元格到其所有相邻单元格都有一条路径.邻居可能会共享一条边或一个角.)

For ex: Suppose I have to search for the word INTELLIGENT in a matrix of characters (3*9) (Once you have picked a character from the matrix to form a sentence, you cannot pick it again to form the same sentence.There is a path from any cell to all its neighboring cells. A neighbor may share an edge or a corner.)

IIIINN.LI  
....TTEGL  
.....NELI  

输出:是(可以找到单词INTELLIGENT) 任何人都可以解决以上问题！！！

Output: YES (the word INTELLIGENT can be found) Can anybody please give a solution to the above problem !!!!

推荐答案

#include <stdio.h>

char Matrix[3][9] = {
    { 'I','I','I','I','N','N','.','L','I'},
    { '.','.','.','.','T','T','E','G','L'},
    { '.','.','.','.',',','N','E','L','I'}
};
char Choice[3][9] = { { 0 }, { 0 }, { 0 } };
const char WORD[] = "INTELLIGENT";
const int  Len = sizeof(WORD)-1;
int Path[sizeof(WORD)-1] = { 0 };

char get(int row, int col){
    if(1 > col || col > 9) return '\0';
    if(1 > row || row > 3) return '\0';
    if(Choice[row-1][col-1] || Matrix[row-1][col-1] == '.')
        return '\0';
    else
        return Matrix[row-1][col-1];
}

#define toLoc(r, c) (r)*10+(c)
#define getRow(L) L/10
#define getCol(L) L%10

int search(int loc, int level){
    int r,c,x,y;
    char ch;
    if(level == Len) return 1;//find it
    r = getRow(loc);
    c = getCol(loc);
    ch = get(r,c);
    if(ch == 0 || ch != WORD[level]) return 0;
    Path[level]=toLoc(r,c);
    Choice[r-1][c-1] = 'v';//marking
    for(x=-1;x<=1;++x){
        for(y=-1;y<=1;++y){
            if(search(toLoc(r+y,c+x), level + 1)) return 1;
        }
    }
    Choice[r-1][c-1] = '\0';//reset
    return 0;
}

int main(void){
    int r,c,i;
    for(r=1;r<=3;++r){
        for(c=1;c<=9;++c){
            if(search(toLoc(r,c), 0)){
                printf("YES\nPath:");
                for(i=0;i<Len;++i){
                    printf("(%d,%d)", getRow(Path[i]), getCol(Path[i]));
                }
                printf("\n");
                return 0;
            }
        }
    }
    printf("NO\n");
    return 0;
}

这篇关于在字符矩阵中搜索特定单词的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！