以任何顺序在矩阵中查找模式？

Question

这是我工作过的一个问题。目标是在字母的二维矩阵中找到模式。美中不足的是，我应该能够找到的格局，即使出现

1. 跨行
2. 跨列
3. 沿

对角线它。

让基质是

A B C D 
E F G H 
I J K L 
M N O P 

我通过取矩阵作为一个字符指针数组写的一个C程序和所用的子串（strstr）来找到模式。我部分成功。我能够在线性化矩阵中寻找连续出现的任何子字符串，但是随后我用对角线元素和交叉元素触及了路障。通过交叉元素我的意思是

我确信，有些算法会在那里将做蛮力找出一个简单的二维矩阵的任何图案。但经过数小时的斗争，我无法想象它。

请建议在接近C.这个问题，我知道使用脚本和基于文本的方法，这将是一个容易的方法，但是我正在寻找能在C.

PS这实现的算法中没有家庭工作问题或工作分配。我很想知道这一切。

Answer 1

我试过将网格存储在char的二维数组中，因为边界条件较少（例如char *指向不同长度的字符串）。无论如何，这是结果。本例中使用的网格是从Types of Dog Word Search“借来的”。

#include <stdio.h> 
#include <string.h> 

static void findword(const char *word, const char *grid, int rows, int cols) 
{ 
    int len = strlen(word); 
    int xdir, ydir, xstart, ystart, xend, yend, xpos, ypos, pos, step, i; 

    for (xdir = -1; xdir <= 1; xdir++) { 
     xstart = xdir < 0 ? len - 1 : 0; 
     xend = xdir > 0 ? cols - len : cols - 1; 
     if (xend < xstart) 
      continue; 
     for (ydir = -1; ydir <= 1; ydir++) { 
      if (ydir == 0 && xdir == 0) 
       continue; 
      ystart = ydir < 0 ? len - 1 : 0; 
      yend = ydir > 0 ? rows - len : rows -1; 
      if (yend < ystart) 
       continue; 
      for (xpos = xstart; xpos <= xend; xpos++) { 
       for (ypos = ystart; ypos <= yend; ypos++) { 
        pos = ypos * cols + xpos; 
        step = ydir * cols + xdir; 
        for (i = 0; i < len; i++) { 
         if (word[i] != grid[pos]) 
          break; 
         pos += step; 
        } 
        if (i == len) { 
         printf("Found %s at row %d, column %d, dir %s%s\n", 
           word, ypos + 1, xpos + 1, 
           ydir < 0 ? "north" : ydir > 0 ? "south" : "", 
           xdir < 0 ? "west" : xdir > 0 ? "east" : ""); 
        } 
       } 
      } 
     } 
    } 
} 

#define GRID_COLS 14 
#define GRID_ROWS (sizeof(wordgrid)/sizeof(wordgrid[0])) 

static const char wordgrid[][GRID_COLS] = { 
    "ESULBULLDOGHER", 
    "EDHISHLSRUDSRE", 
    "IARELIEWTTORRE", 
    "RLGTLAEITCORGI", 
    "EMRDERIISLEPCF", 
    "HARSCANHHHLEHF", 
    "CTREDOETOEGBII", 
    "SIETLPLUHEATHT", 
    "NAITHXNLAUECUS", 
    "INRELDEEIBBOAA", 
    "PNRREOADREHGHM", 
    "UDEAAERHIAFRUI", 
    "BRTOBOXERHTSAI", 
    "LELAMSLRLHUDRL" 
}; 

#define NUM_WORDS (sizeof(words)/sizeof(words[0])) 

static const char * const words[] = { 
    "CHIHUAHUA", "BULLDOG", "TERRIER", "COLLIE", "SHEPHERD", "BOXER", 
    "HOUND", "BEAGLE", "CORGI", "ROTTWEILER", "PINSCHER", "DALMATIAN", 
    "SETTER", "MASTIFF" 
}; 

int main(void) 
{ 
    int i; 

    printf("Grid:\n\n"); 
    for (i = 0; i < GRID_ROWS; i++) 
     printf("%.*s\n", GRID_COLS, wordgrid[i]); 
    printf("\n"); 
    for (i = 0; i < NUM_WORDS; i++) { 
     printf("*** Looking for %s ***\n", words[i]); 
     findword(words[i], &wordgrid[0][0], GRID_ROWS, GRID_COLS); 
    } 
    return 0; 
} 

可能有更有效的算法，诸如搜索网格的单词的第一个字母，然后检查八个方向上的字的剩余字母（与不可能方向根据网格位置，并过滤出字长）。

Answer 2

（我打电话这个伪 - 集结矩阵等这样是不正确。）

int match(char** matrix, int width, int height, int x, int y, char *str, int strPos, int strLen, int dx, int dy) 
{ 

    if (strPos == strLen) 
     return 1; 

    int i = x + dx; 
    int j = y + dy; 

    if (i < 0 || i >= width || j < 0 || j >= height || strPos > strLen) 
     return 0; 

    /// fix this... 
    char mc = matrix[x][y]; 

    if (mc != str[strPos]) 
     return 0; 

    return match(matrix, width, height, i, j, str, strPos + 1, strLen, dx, dy); 
} 

int matches(char** matrix, int width, int height, char* str, int strLen) 
{ 
    for (int i = 0; i < matrixWidth; ++i) 
    { 
     for (int j = 0; j < matrixHeight; ++j) 
     { 
      if (matrix[i][j] != str[0]) 
       continue; 

      for (int dx = -1; dx <= 1; ++dx) 
      { 
       for (int dy = -1; dy <= 1; ++dy) 
       { 
        if (match(matrix, matrixWidth, matrixHeight, i, j, dx, dy)) 
         return 1; 
       } 
      } 
     } 
    } 

    return 0; 



} 

这可能是丢失了一些边界检查，并可以通过只检查一个方向（DX进行优化，dy）如果字符串可以适合而不超出矩阵范围。

这与洪水填充非常相似，额外的约束条件是检查必须从初始递归调用中进入单一方向，而不是螺旋出来。