如何在字符矩阵中查找字符串路径？

Question

你将如何去实现一个函数来检查字符矩阵中是否存在字符串的路径？它在矩阵中向左，向右，向上和向下移动，并移动一个单元格。

该路径可以从矩阵中的任何条目开始。如果一个单元格被路径上的一个字符串的字符占用，则它不能再被另一个字符占用。

你将如何去解决这个问题（如果你愿意，伪码）？我最初的想法是将其解释为一个图形问题，矩阵位置作为图形中的一个顶点。

Answer 1

编辑：添加一个慢半java的半伪代码版本

class Pair { 
    public Pair(int x, int y) { this.x = x; this.y = y; } 
    public int x; 
    public int y; 
}; 

class Main { 
    static Vector<Pair> singleton(Pair p) { 
     Vector<Pair> v = new Vector<Pair>(); 
     v.insert(p); 
     return v; 
    } 

    static void f(String str, int [][]matrix, int width, int height) { 
     Vector<Vector<Pair>> v = new Vector<Vector<Pair>>(); 
     for (int i = 0; i < height; ++i) 
      for (int j = 0; j < width; ++j) 
       try(i, j, str, matrix, width, height, v); 
    } 

    static void try(int i, int j, String str, int [][]matrix, int width, int height, Vector<Vector<Pair>> v) { 
     int old_v_size = v.length; 
     if (i < 0 || i >= height || j < 0 || j >= width) return; 
     if (str.length == 1) v.insert(singleton(new Pair(i,j)); 
     try(i+1,j,str.substr(1),matrix,width,height,v); 
     try(i-1,j,str.substr(1),matrix,width,height,v); 
     try(i,j+1,str.substr(1),matrix,width,height,v); 
     try(i,j-1,str.substr(1),matrix,width,height,v); 
     for (int k = old_v_size; k < v.length; ++k) v[k].insert(new Pair(i,j)); 
    } 

} 

旧代码如下所示：

这是在Haskell（我有一个函数在这里更换矩阵的解决方案获得两个整数并返回矩阵中的值）。函数f接受字符串，矩阵函数，宽度和高度，并为每个可能的解决方案返回元组列表的列表。

f str matrix width height = 
    concat [try i j str matrix width height | i <- [0..width-1], j <- [0..height-1] ] 


try i j (c:cs) matrix width height | i < 0 || 
            i >= height || 
            j < 0 || 
            j >= width || 
            matrix i j /= c = [] 
try i j [c] matrix width height = [(i,j)] 
try i j (c:cs) matrix width height = 
    concat [map ((i,j):) $ try (i+1) j cs matrix width height, 
      map ((i,j):) $ try (i-1) j cs matrix width height, 
      map (c:) $ try i (j+1) cs matrix width height, 
      map (c:) $ try i (j-1) cs matrix width height] 

如果你想要另一种语言请注明，我会送另一种解决方案

Answer 2

public class MatrixSearch { 

    public static void main(String[] args) { 

     String[] find = {"M", "I", "C", "R", "O", "S", "O", "F", "T"}; 

     String[][] matrix = { 
      {"A", "C", "P", "R", "C"}, 
      {"M", "S", "O", "P", "C"}, 
      {"I", "O", "V", "N", "I"}, 
      {"C", "G", "F", "M", "N"}, 
      {"Q", "A", "T", "I", "T"} 
     }; 
     // printing matrix... 
     for (int i = 0; i < matrix.length; i++) { 
      for (int j = 0; j < matrix[i].length; j++) { 
       System.out.print(matrix[i][j]); 
      } 
      System.out.println(""); 
     } 
     for (int i = 0; i < matrix.length; i++) { 
      for (int j = 0; j < matrix[i].length; j++) { 
       if (matrix[i][j].equals(find[0])) { 
        System.out.println(matrix[i][j]); 
        boolean found = recursiveMatrixFind(matrix, i, j, matrix.length, matrix.length, find, 1);      
        System.out.println(found); 
       } 
      } 
     } 
    } 

    public static boolean recursiveMatrixFind(String[][] matrix, int row, int column, int rowLength, int columnLength, String[] find, int k) { 

     if (k == find.length) { 
      return true; 
     } 

     for (int neighbourRow = row - 1; neighbourRow <= row + 1; neighbourRow++) { 
      if (neighbourRow >= 0 && neighbourRow < rowLength) { 
       for (int neighbourColumn = column - 1; neighbourColumn <= column + 1; neighbourColumn++) { 
        if (neighbourColumn >= 0 && neighbourColumn < columnLength) { 
         if ((!(neighbourRow == row && neighbourColumn == column))) { 
          if (matrix[neighbourRow][neighbourColumn].equals(find[k])) { 
           System.out.println(matrix[neighbourRow][neighbourColumn]); 
           boolean found = recursiveMatrixFind(matrix, neighbourRow, neighbourColumn, rowLength, columnLength, find, ++k); 
           if (found) { 
            return true; 
           } else { 
            continue; 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
     return false; 
    } 
}