你得到了一个MXN阵列。9号是奶酪，0号是墙，1号是路你就是鼠标，从左上角开始a[0][0]。你需要知道有没有通向奶酪的路。这就是我被问到的问题。我试着用某种方法解决它，我想知道是否有人能告诉我它是正确的还是走在正确的道路上，因为我有点一时冲动，在考试中没有时间了。
我的想法是，如果你知道你从左上角开始，那么你只需要向下和向右移动，如果数组看起来是这样的：
1 0 0 0
1 1 0 0
0 1 1 9
0 0 0 0
所以左上角是1，这意味着存在一条路径，所以我所做的是在左、右相邻的单元提供的左上角递归，生成2个子数组。所以我在这两个子数组上调用了ispath方法
0 0 0
1 0 0
1 1 9
0 0 0
然后
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)
}
}
这是解决这个问题的正确方法吗？或者我错过了什么
编辑：没有助手方法
最佳答案
我想你忘了这样的排列：
1 0 0 9
1 1 0 1
0 1 1 1
0 0 0 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种方法合并在一起。在这里，我试图解释不编写优化代码的解决方案。
关于java - 在阵列迷宫中找到“奶酪”，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31633229/