我试图通过C在字符矩阵中搜索特定单词,但无法找到固定的解决方案。
例如:假设我必须在字符矩阵(3 * 9)中搜索单词INTELLIGENT(一旦你从矩阵中选择了一个字符来形成一个句子,你就不能再选择它来形成同一个句子。有从任何单元到其所有相邻单元的路径。一个邻居可以共享一条边或一个角。)
ⅢNN.LI ....TTEGL .....内力
输出:YES(可以找到INTELLIGENT这个词)任何人都可以解决上述问题!!!!
使用深度优先搜索。
您可以使用递归算法来做到这一点。找到包含第一个字母的所有(未使用的)位置,然后从相邻的一个方格开始,看看是否可以在剩余的板上找到单词的其余部分。
#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;
}
我想这就是你的意思.....虽然它看起来比你目前提供的更简单,所以我可能误解了这个问题。
我使用 Numpy 将任意数组重塑为单个字母列表,然后我们创建搜索词的掩码和输入列表的副本。我在更新掩码时勾选要搜索的每个字母。
将 numpy 导入为 np 导入副本 def findInArray(I,Word): M=[list(x) for x in I] M=列表(np.ravel(M)) print "开始的字母:%s"%"".join(M) 掩码=[假]*len(字) T = copy.copy(M) 对于 enumerate(Word) 中的 n,v: 尝试: p=T.index(v) 除了ValueError: 经过 别的: T[p]='' 掩码[n]=真 print "剩余的字母:%s"%"".join(T) if all(Mask):print "Found %s"%Word else:print "%s not Found"%Word 打印“\n” 全部归还(面具) 我=["IIIINN.LI","....TTEGL","....NELI"] findInArray(I,"INTEL") findInArray(I,"智能") findInArray(I,"智能")
示例输出
开头的字母:IIIN.LI....TTEGL.....NELI 剩余
的字母:IIIN.I....TGL.....NELI
找到 INTEL
开始的字母: IIIINN.LI....TTEGL....NELI 剩余
的字母:II.I..........NLI
发现 INTELLIGENT
开始的字母: IIIINN.LI....TTEGL.....NELI 剩余
的字母:II.I....T.......NLI
未找到智能
#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;
}