小红拿到了一个字符矩阵，矩阵仅由’r’、’e’、’d’三种字符组成。她初始站在左上角，每次可以走到一个相邻的字符上（每个字符上、下、左、右最多4个相邻）。但有个限制，小红不能从’r’走到’d’，从’e’走到’r’，从’d’走到’e’，其他情况都能走。 小红想知道，从左上角走到右下角至少需要多少步？
区块链毕设网qklbishe.com为您提供问题的解答
小红拿到了一个字符矩阵，矩阵仅由’r’、’e’、’d’三种字符组成。她初始站在左上角，每次可以走到一个相邻的字符上（每个字符上、下、左、右最多4个相邻）。但有个限制，小红不能从’r’走到’d’，从’e’走到’r’，从’d’走到’e’，其他情况都能走。
小红想知道，从左上角走到右下角至少需要多少步？
import java.util.Scanner; import java.util.Map; import java.util.HashMap; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static int res = -1; public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 int m = in.nextInt(); int n = in.nextInt(); char[][] arr = new char[m][n]; for (int i=0; i<m; i++) { String str = in.next(); for (int j = 0; j<n; j++) { arr[i][j] = str.charAt(j); } } int[][] dp = new int[m][n]; Map<Character, Character> map = new HashMap<>(); map.put('r', 'd'); map.put('e', 'r'); map.put('d', 'e'); dfs(0, 0, arr, 0, dp, map); System.out.println(res); } public static void dfs(int i, int j, char[][] arr, int steps, int[][]dp, Map<Character, Character>map) { if (i==arr.length-1 && j==arr[0].length-1) { if (res == -1) { res = steps; return; } res = Math.min(res, steps); return; } // if (i+1 >= arr.length && i-1<0 && j+1>=arr[0].length && j-1<0) { // return; // } if (i+1 < arr.length && dp[i+1][j] ==0 && checkWalk(arr[i][j], arr[i+1][j], map)) { dp[i+1][j] = 1; dfs(i+1, j, arr, steps+1, dp, map); dp[i+1][j] = 0; if (res == steps + arr.length - i + arr[0].length - j - 2) { return; } } if (j+1 < arr[0].length && dp[i][j+1] ==0 && checkWalk(arr[i][j], arr[i][j+1], map)) { dp[i][j+1] = 1; dfs(i, j+1, arr, steps+1, dp, map); dp[i][j+1] = 0; if (res == steps + arr.length - i + arr[0].length - j - 2) { return; } } if (res == -1) { if (i-1 >= 0 && dp[i-1][j] ==0 && checkWalk(arr[i][j], arr[i-1][j], map)) { dp[i-1][j] = 1; dfs(i-1, j, arr, steps+1, dp, map); dp[i-1][j] = 0; if (res == steps + arr.length - i + arr[0].length - j - 2) { return; } } if (j-1 >= 0 && dp[i][j-1] ==0 && checkWalk(arr[i][j], arr[i][j-1], map)) { dp[i][j-1] = 1; dfs(i, j-1, arr, steps+1, dp, map); dp[i][j-1] = 0; if (res == steps + arr.length - i + arr[0].length - j - 2) { return; } } } } public static boolean checkWalk(char a, char b, Map<Character, Character>map) { if (!map.containsKey(a)) { return true; } return map.get(a) != b; } }
dfs做了一些优化，但还是超时
39:51
以上就是关于问题小红拿到了一个字符矩阵，矩阵仅由’r’、’e’、’d’三种字符组成。她初始站在左上角，每次可以走到一个相邻的字符上（每个字符上、下、左、右最多4个相邻）。但有个限制，小红不能从’r’走到’d’，从’e’走到’r’，从’d’走到’e’，其他情况都能走。
小红想知道，从左上角走到右下角至少需要多少步？的答案
欢迎关注区块链毕设网-
web3一级市场套利打新赚钱空投教程
区块链NFT链游项目方科学家脚本开发培训
.jpg){kind=link}