搜索字符矩阵中的特定单词
我试图通过C搜索字符矩阵中的特定单词，但无法找到固定的解决方案。
例如：假设我必须在字符矩阵中搜索单词INTELLIGENT （3 * 9）（一旦你从矩阵中选择一个字符形成一个句子，你就不能再选择它来形成同一个句子。有从任何小区到其所有相邻小区的路径。邻居可以共享边缘或角落。）
IIIINN.LI .... TTEGL ..... NELI
输出：是（可以找到智能这个词）任何人都可以解决上述问题!!!!
#include 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 使用深度优先搜索。
你可以使用递归算法来做到这一点。 找到包含第一个字母的所有（未使用的）位置，然后查看是否可以通过从相邻的一个方块开始在剩余的板上找到剩余的字。
我认为这就是你的意思…..虽然你现在提供的东西似乎更简单，所以我可能误解了这个问题。
我使用Numpy将任意数组重新整形为单个字母列表，然后我们创建搜索项的掩码和输入列表的副本。 我勾选每个字母以便在更新面具时进行搜索。
导入numpy为np
import副本
def findInArray（I，Word）：
M = [I中x的列表（x）]
M =列表（np.ravel（M））
print“要开始的信件：％s”％“”。join（M）
掩模= [FALSE] * LEN（字）
T = copy.copy（M）
for n，v in enumerate（Word）：
尝试：
P = T.index（v）的
除了ValueError：
通过
其他：
T [P] = ''
面膜[N] = TRUE
打印“留下的字母：％s”％“”。join（T）
if all（Mask）：打印“找到％s”％Word
else：打印“％s not found”％Word
打印“\ n”
全部返回（面具）
I = [ “IIIINN.LI”， “.... TTEGL”， “..... NELI”]
findInArray（I， “英特尔”）
findInArray（I， “智能”）
findInArray（I， “智能”）
示例输出
信件开始：IIIINN.LI …. TTEGL ….. NELI
遗留下来的信件：IIIN.I …. TGL ….. NELI
发现INTEL
信件开始：IIIINN.LI …. TTEGL ….. NELI
遗留下来的信件：II.I ……… NLI
发现智能
信件开始：IIIINN.LI …. TTEGL ….. NELI
遗留下来的信件：II.I …. T ….. NLI
未找到智能
#include #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