Поиск определенного слова в матрице символов

Question

Я пытался найти конкретное слово в матрице символов через C, но не смог найти фиксированное решение.

Для бывших: Предположим, что я должен искать слова ИНТЕЛЛЕКТ в матрице символов (3 * 9) (После того, как вы выбрали символ из матрицы, чтобы сформировать предложение, вы не можете забрать его снова чтобы сформировать то же самое sentence.There путь из любой клетки для всех соседних ячеек сосед может разделять край или угол)

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

Выход:.. ДА (слово ИНТЕЛЛЕКТ можно найти) Can кто-нибудь, пожалуйста, дайте решение вышеупомянутой проблемы !!!!

Answer 1

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

Answer 2

Используйте поиск глубины вначале.

Вы можете сделать это, используя рекурсивный альгортм. Найдите все (неиспользуемые) места, содержащие первую букву, затем посмотрите, можно ли найти остальную часть слова на оставшейся доске, начиная с одного из смежных квадратов.

Answer 3

Я думаю, что это то, что вы имеете в виду ..... Хотя это кажется проще, что вы в настоящее время были предложены, так что я, возможно, неправильно понял вопрос.

Я использую Numpy для изменения произвольного массива в один список букв , затем мы создаем маску поискового запроса и копию списка входных данных. Я отмечаю каждую букву для поиска при обновлении маски.

 

import numpy as np 
import copy 

def findInArray(I,Word): 
    M=[list(x) for x in I] 

    M=list(np.ravel(M)) 

    print "Letters to start: %s"%"".join(M) 

    Mask=[False]*len(Word) 

    T = copy.copy(M) 

    for n,v in enumerate(Word): 
     try: 
      p=T.index(v) 
     except ValueError: 
      pass 
     else: 
      T[p]='' 
      Mask[n]=True 

    print "Letters left over: %s"%"".join(T)    
    if all(Mask):print "Found %s"%Word 
    else:print "%s not Found"%Word 

    print "\n" 

    return all(Mask) 


I=["IIIINN.LI","....TTEGL",".....NELI"] 

findInArray(I,"INTEL") 
findInArray(I,"INTELLIGENT") 
findInArray(I,"INTELLIGENCE") 

Пример выходных

Письма, чтобы начать: IIIINN.LI .... TTEGL ..... NELI
письма осталось: IIIN.I .... TGL ..... NELI
Найдено INTEL

Письма начать: IIIINN.LI .... TTEGL ..... Нели
письма осталось: II.I ......... NLI
Найдено ИНТЕЛЛЕКТ

Письма начать: IIIINN.LI .... TTEGL ..... Нели
письма осталось : II.I .... T ..... NLI
ИНТЕЛЛЕКТ не найдено

Answer 4

#include <stdio.h> 

#define ROW 1 
#define COL 11 

char Matrix[ROW][COL] = { { 'I','N','T','E','L','L','I','G','E', 'N', 'T'} }; 
char Choice[ROW][COL] = { { 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 > COL) return '\0'; 
    if(1 > row || row > ROW) 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)*16+(c) 
#define getRow(L) L/16 
#define getCol(L) L%16 

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<=ROW;++r){ 
     for(c=1;c<=COL;++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; 
}