英文:
Min cost in maze traversal using recursion (please find the issue in below mention solution)
问题
请帮我找出我在这个解决方案中犯了什么错误，因为我的输出是错误的。提前致谢。
- 给定一个数字 n，表示行数。
- 给定一个数字 m，表示列数。
- 给定 n*m 个数字，表示 2D 数组 a 的元素，它表示一个迷宫。
- 你站在左上角的单元格，并需要移动到右下角的单元格。
- 你可以在一次动作中向右移动 1 个单元格（水平移动）或向下移动 1 个单元格（垂直移动）。
- 每个单元格都有一个值，必须支付该值才能进入该单元格（即使是左上角和右下角的单元格）。
- 你需要遍历矩阵并打印最少代价的路径。
// 调用递归函数 findMinCost 来减少行和列，并找到其中的最小代价
public static int findMinCost(int[][] maze, int row, int col) {
if(row == 0 && col == 0) {
return maze[row][col];
}
int cost = 0;
if(row >= 0 && col >= 0) {
cost += Integer.min(findMinCost(maze, row-1, col),findMinCost(maze, row, col-1))+maze[row][col];
}
return cost;
}
英文:
Please help me in finding that where I am doing the mistake in this solution as my output is coming wrong. thanks in advance.
- You are given a number n, representing the number of rows.
- You are given a number m, representing the number of columns.
- You are given n*m numbers, representing elements of 2d array a, which represents a maze.
- You are standing in top-left cell and are required to move to bottom-right cell.
- You are allowed to move 1 cell right (h move) or 1 cell down (v move) in 1 motion.
- Each cell has a value that will have to be paid to enter that cell (even for the top-left and bottom-
right cell). - You are required to traverse through the matrix and print the cost of path which is least costly.
// making the recursive call to findMinCost by reducing the row and column and finding the min cost out of that
public static int findMinCost(int[][] maze, int row, int col) {
if(row == 0 && col == 0) {
return maze[row][col];
}
int cost = 0;
if(row >= 0 && col >=0) {
cost += Integer.min(findMinCost(maze, row-1, col),findMinCost(maze, row, col-
1))+maze[row][col];
}
return cost;
}
答案1
得分: 0
主要问题是，当坐标中的一个或两个变为负数时（这一定会发生），您的函数返回0作为成本。这是不正确的，因为零可能是一个有趣的成本选择。在这种情况下，搜索会超出迷宫，这应该是不可能的：因此，在这种情况下返回一个极高的成本，而不是0。
修复方法很简单：在第二个if块中添加一个else块：
} else return Integer.MAX_VALUE;
现在它将适用于小型迷宫。（我假设您在调用函数时正确使用row和col引用迷宫中右下角的单元格）
对于较大的迷宫，您将遇到时间问题，因为这个算法将一遍又一遍地重新访问相同的子路径。您可以通过使用记忆化来解决这个问题。
英文:
The main problem is that when one or both of the coordinates become negative (and this will happen), your function returns 0 as cost. This is not correct, as zero might be an interesting cost to go for. In this case a search is made outside the maze and that should be made impossible: so return an extreme high cost in that case, not 0.
The fix is simple: add an else block to your second if block:
} else return Integer.MAX_VALUE;
Now it will work for small mazes. (I assume you correctly call your function with row and col referencing the bottom-right cell in the maze)
For larger mazes you will run into a timing problem, since this algorithm will revisit the same sub-paths over and over again. You can solve this by using memoization.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论