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

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]