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

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