在数组迷宫中找到 "cheese"

Question

你得到了一个 mxn 数组。数字 9 是奶酪，数字 0 是墙，数字 1 是路径。你是鼠标，从左上角 a[0][0] 开始。你需要找出是否有通往奶酪的路径。这是我被问到的问题。我尝试以某种方式解决它，我想知道是否有人可以告诉我它是否正确或是否在正确的道路上，因为我有点一时兴起并且运行在测试中超时。

我的想法是，如果你知道你从左上角开始，那么如果数组如下所示，你只需要向下和向右移动：

所以左上角是1，这意味着存在路径，所以我所做的是在左右相邻单元格提供的左上角递归，创建2个子数组。所以我在这两个子数组上调用了 isPath 方法

然后

1 1 0 0 
0 1 1 9
0 0 0 0

该方法的基本版本如下所示：

isPath(int[][] matrix) {
    if(matrix[0][0] == 0)
        return 0;
    if(matrix[0][0] == 9)
        return 1; //found
    if(matrix[0][0] == 1) {
        subarray1 = copy starting from matrix[0][1]
        subarray2 = copy starting from matrix[1][0]
        isPath(subarray1)
        isPath(subarray2)
    }
}

这是解决这个问题的正确方法吗？还是我遗漏了什么

编辑：没有辅助方法

Answer 1

我想你忘记了这样的数组：

你的递归函数在前面的例子中不会完成，请检查数组的大小以完成递归。

还有你的算法没有用完和找奶酪

编辑

你应该处理好4个方向，不要重复你之前访问过的广场，我会在这里添加伪代码来解释解决方案的主要思路：

public class MAZE {

    static int x, y;
    static boolean result = false;

    public static void main(String[] args) {
        int [][] matrix =new int[5][];// fill your array
        // fill x and y
        // x= cheese x value
        // y = cheese y value
        isPath(matrix, x, x);
        // print result


    }

    static void isPath(int[][] matrix, int i, int j) {
        if (i - 1 > -1 && matrix[i - 1][j] == 1) {
            // subarray1 = copy starting from [0][0] to matrix[i-1][j]
            // checkSPath(subarray1,i-1,j);
        }
        if (j - 1 > -1 &&  matrix[i][j - 1] == 1) {
            // subarray1 = copy starting from [0][0] to matrix[i][j-1]
            // checkLPath(subarray1,i,j-1);
        }

        if (i + 1 < x && matrix[i + 1][j] == 1) {
            // subarray1 = copy starting from [0][0] to matrix[i+1][j]
            // checkNPath(subarray1,i+1,j);
        }
        if (j + 1 < y &&  matrix[i][j + 1] == 1) {
            // subarray1 = copy starting from [0][0] to matrix[i][j+1]
            // checkRPath(subarray1,i,j+1);
        }
    }

    static void checkRPath(int[][] matrix, int i, int j) {
        if (i == 0 && j == 0) {
            result = true;
        } else {
            if (i - 1 > -1 && matrix[i - 1][j] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i-1][j]
                // checkSPath(subarray1,i-1,j);
            }

            if (i + 1 < x && matrix[i + 1][j] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i+1][j]
                // checkNPath(subarray1,i+1,j);
            }
            if (j + 1 < y && matrix[i][j + 1] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i][j+1]
                // checkRPath(subarray1,i,j+1);
            }
        }
    }

    static void checkLPath(int[][] matrix, int i, int j) {

        if (i == 0 && j == 0) {
            result = true;
        } else {
            if (i - 1 > -1 && matrix[i - 1][j] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i-1][j]
                // checkSPath(subarray1,i-1,j);
            }
            if (j - 1 > -1 && matrix[i][j - 1] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i][j-1]
                // checkLPath(subarray1,i,j-1);
            }

            if (i + 1 < x && matrix[i + 1][j] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i+1][j]
                // checkNPath(subarray1,i+1,j);
            }
        }
    }

    static void checkNPath(int[][] matrix, int i, int j) {
        if (i == 0 && j == 0) {
            result = true;
        } else {
            if (j - 1 > -1 && matrix[i][j - 1] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i][j-1]
                // checkLPath(subarray1,i,j-1);
            }

            if (i + 1 < x && matrix[i + 1][j] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i+1][j]
                // checkNPath(subarray1,i+1,j);
            }
            if (j + 1 < y && matrix[i][j + 1] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i][j+1]
                // checkRPath(subarray1,i,j+1);
            }
        }

    }

    static void checkSPath(int[][] matrix, int i, int j) {
        if (i == 0 && j == 0) {
            result = true;
        } else {
            if (i - 1 > -1 && matrix[i - 1][j] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i-1][j]
                // checkSPath(subarray1,i-1,j);
            }
            if (j - 1 > -1 && matrix[i][j - 1] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i][j-1]
                // checkLPath(subarray1);
            }

            if (j + 1 < y && matrix[i][j + 1] == 1) {
                // subarray1 = copy starting from [0][0] to matrix[i][j+1]
                // checkRPath(subarray1);
            }
        }
    }
}

您可以将这 5 种方法合二为一。在这里，我试图解释不编写优化代码的解决方案。

在数组迷宫中找到 "cheese"

Finding the "cheese" in an array maze

java

algorithm

maze