小红拿到了一个行列的二维矩阵，矩阵的元素都是正整数。 小红站在矩阵的左上角，她每一步可以走上、下、左、右四种方向中的一个，花费的时间为这两个相邻元素的差的绝对值。另外，小红最多可以使用一次传送阵，不花费任何时间，从一个数到达另一个相同的数。 小红想知道， 自己从左上角走到右下角最少需要多少时间？
区块链毕设网qklbishe.com为您提供问题的解答
小红拿到了一个行
列的二维矩阵，矩阵的元素都是正整数。
小红站在矩阵的左上角，她每一步可以走上、下、左、右四种方向中的一个，花费的时间为这两个相邻元素的差的绝对值。另外，小红最多可以使用一次传送阵，不花费任何时间，从一个数到达另一个相同的数。
小红想知道， 自己从左上角走到右下角最少需要多少时间？
回溯法，超时了
import java.util.Map; import java.util.Scanner; import java.util.HashMap; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { static long min = 9999999999l; public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int[][] matrix = new int[n][m]; boolean[][] arrived = new boolean[n][m]; int i = 0; // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { // 注意 while 处理多个 case matrix[i / m][i % m] = in.nextInt(); i++; } backtrace(matrix, arrived, 0, 0, n, m, false, 0); System.out.println(min); } static void backtrace(int[][] matrix, boolean[][] arrived, int x, int y, int m, int n, boolean transport, long time) { if (x == m - 1 && y == n - 1) { if (time < min) { min = time; } return; } if (x + 1 < m && !arrived[x + 1][y]) { int cost = Math.abs(matrix[x + 1][y] - matrix[x][y]); arrived[x + 1][y] = true; backtrace(matrix, arrived, x + 1, y, m, n, transport, time + cost); arrived[x + 1][y] = false; } if (x - 1 >= 0 && !arrived[x - 1][y]) { int cost = Math.abs(matrix[x - 1][y] - matrix[x][y]); arrived[x - 1][y] = true; backtrace(matrix, arrived, x - 1, y, m, n, transport, time + cost); arrived[x - 1][y] = false; } if (y + 1 < n && !arrived[x][y + 1]) { int cost = Math.abs(matrix[x][y + 1] - matrix[x][y]); arrived[x ][y + 1] = true; backtrace(matrix, arrived, x, y + 1, m, n, transport, time + cost); arrived[x][y + 1] = false; } if (y - 1 >= 0 && !arrived[x][y - 1]) { int cost = Math.abs(matrix[x][y - 1] - matrix[x][y]); arrived[x ][y - 1] = true; backtrace(matrix, arrived, x, y - 1, m, n, transport, time + cost); arrived[x][y - 1] = false; } if(!transport) { for(int i = 0; i<m; i++) { for(int j =0;j<n;j++) { if(matrix[i][j] == matrix[x][y] && !arrived[i][j]) { arrived[i][j] = true; backtrace(matrix, arrived, i, j, m, n, true, time ); arrived[i][j] = false; } } } } } }
编辑于 今天 01:36:44
以上就是关于问题小红拿到了一个行列的二维矩阵，矩阵的元素都是正整数。
小红站在矩阵的左上角，她每一步可以走上、下、左、右四种方向中的一个，花费的时间为这两个相邻元素的差的绝对值。另外，小红最多可以使用一次传送阵，不花费任何时间，从一个数到达另一个相同的数。
小红想知道， 自己从左上角走到右下角最少需要多少时间？的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
.jpg){kind=link}