一个大小为N*N，并且有若干个陷阱的迷宫，X星人现在站在迷宫左上角的起点(第1行第1列)，迷宫的终点是右下角(第N行第N列)。 X星人每次可以朝上、下、左、右四个方向行走，但不允许穿越墙壁。 在迷宫中，“0”表示空地，“1”表示墙壁，“#”表示陷阱。X星人在迷宫中每行走一步需要1秒钟，但如果不幸掉入陷阱，则需要额外增加K秒的 逃脱时间。如果终点位置恰好是陷阱，也需要计算时间。 假设起点(左上角)既不是墙也不是陷阱，请问X星人从起点到终点最少需要多少时间?
区块链毕设网qklbishe.com为您提供问题的解答
一个大小为N*N，并且有若干个陷阱的迷宫，X星人现在站在迷宫左上角的起点(第1行第1列)，迷宫的终点是右下角(第N行第N列)。 X星人每次可以朝上、下、左、右四个方向行走，但不允许穿越墙壁。 在迷宫中，“0”表示空地，“1”表示墙壁，“#”表示陷阱。X星人在迷宫中每行走一步需要1秒钟，但如果不幸掉入陷阱，则需要额外增加K秒的 逃脱时间。如果终点位置恰好是陷阱，也需要计算时间。 假设起点(左上角)既不是墙也不是陷阱，请问X星人从起点到终点最少需要多少时间?
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; static int minL = Integer.MAX_VALUE; static int k; static int n; public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 n = in.nextInt(); k = in.nextInt(); char[][] board = new char[n][n]; boolean[][] used = new boolean[n][n]; used[0][0] = true; for(int i = 0 ; i < n ; i++){ String str = in.next(); for(int j = 0 ; j < 3 ; j++){ board[i][j] = str.charAt(j); } } if(board[n - 1][n - 1] == '1'){ System.out.println("No solution"); return; } dfs(0, 0, board, used, 0); if(minL == Integer.MAX_VALUE){ System.out.println("No solution"); }else{ System.out.println(minL); } } public static void dfs(int i, int j, char[][] board, boolean[][]used, int time){ if(i == board.length - 1 && j == board.length - 1){ minL = Math.min(minL, time); return; } for(int k = 0 ; k < 4 ; k++){ int x = dir[k][0] + i; int y = dir[k][1] + j; if(x < 0 || y < 0 || x >= n || y >= n || used[x][y] || board[x][y] == '1') continue; if(board[x][y] == '0'){ used[x][y] = true; dfs(x, y, board, used, time + 1); used[x][y] = false; } if(board[x][y] == '#'){ used[x][y] = true; dfs(x, y, board, used, time + k); used[x][y] = false; } } } }
编辑于 2024-04-15 21:28:08
以上就是关于问题一个大小为N*N，并且有若干个陷阱的迷宫，X星人现在站在迷宫左上角的起点(第1行第1列)，迷宫的终点是右下角(第N行第N列)。 X星人每次可以朝上、下、左、右四个方向行走，但不允许穿越墙壁。 在迷宫中，“0”表示空地，“1”表示墙壁，“#”表示陷阱。X星人在迷宫中每行走一步需要1秒钟，但如果不幸掉入陷阱，则需要额外增加K秒的 逃脱时间。如果终点位置恰好是陷阱，也需要计算时间。 假设起点(左上角)既不是墙也不是陷阱，请问X星人从起点到终点最少需要多少时间?的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
