全网最全面的华为OD机试真题汇总,100%原题题库,不需要开会员即可查看全部内容,更多考题请查看真题库。
真题库:https://www.yuque.com/codernav.com/od
题目:上班之路
知识点BFS搜索广搜
时间限制:1s 空间限制:256MB 限定语言:不限
题目描述:
Jungle生活在美丽的蓝鲸城,大马路都是方方正正,但是每天马路的封闭情况都不一样。
地图由以下元素组成:
1)”.” — 空地,可以达到;
2)”*” — 路障,不可达到;
3)”S” — Jungle的家;
4)”T” — 公司.
其中我们会限制Jungle拐弯的次数,同时Jungle可以清除给定个数的路障,现在你的任务是计算Jungle是否可以从家里出发到达公司。
输入描述:
输入的第一行为两个整数t,c(0<=t,c<=100), t代表可以拐弯的次数,c代表可以清除的路障个数。
输入的第二行为两个整数n,m(1<=n,m<=100),代表地图的大小。
接下来是n行包含m个字符的地图。n和m可能不一样大。
我们保证地图里有S和T。
输出描述:
输出是否可以从家里出发到达公司,是则输出YES,不能则输出NO。
示例1
输入:
2 0
5 5
..S..
****.
T….
****.
…..
输出:
YES
示例2
输入:
1 2
5 5
.*S*.
*****
..*..
*****
T….
输出:
NO
说明:
该用例中,至少需要拐弯1次,清除3个路障,所以无法到达
解题思路:
通过回溯法求出所有可能的路径。
真实测试用例:
1 2 0 5 5 ..S.. ****. T…. ****. ….. YES
2 1 2 5 5 .*S*. ***** ..*.. ***** T…. NO
6 1 1 3 3 T.* *.* *S* YES
9 0 0 2 4 S.*T *… NO
代码实现一:
package com.codernav.demo.hwod.exam; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * @title 上班之路 * @Description Jungle生活在美丽的蓝鲸城,大马路都是方方正正,但是每天马路的封闭情况都不一样。 * 地图由以下元素组成: * 1)"." — 空地,可以达到; * 2)"*" — 路障,不可达到; * 3)"S" — Jungle的家; * 4)"T" — 公司. * 其中我们会限制Jungle拐弯的次数,同时Jungle可以清除给定个数的路障,现在你的任务是计算Jungle是否可以从家里出发到达公司。 * @Author 开发者导航 * @website https://codernav.com * @date 2023/5/28 */ public class Main { public static char[][] map; //地图 public static int t; //转弯次数 public static int c; //路障个数 public static int n; //地图行数 public static int m; //地图列数 public static void main(String[] args) { Scanner sc = new Scanner(System.in); t = sc.nextInt(); c = sc.nextInt(); n = sc.nextInt(); m = sc.nextInt(); sc.nextLine(); map = new char[n][m]; char[][] mapCopy = new char[n][m]; int x = 0; int y = 0; for (int i = 0; i < n; i++) { String string = sc.nextLine(); for (int j = 0; j < m; j++) { map[i][j] = string.charAt(j); mapCopy[i][j] = map[i][j]; if (map[i][j] == 'S') { x = i; y = j; } } } if (toCompany(mapCopy, x, y, new ArrayList<>(), 0, 0) == 1) { System.out.println("YES"); } else { System.out.println("NO"); } } /** * @param newMap 地图,用来记录走过的行程 * @param x 横坐标 * @param y 纵坐标 * @param list 走过的坐标集合 * @param turn 转弯的次数 * @param barricade 路过路障的次数 * @return */ public static int toCompany(char[][] newMap, int x, int y, List<int[]> list, int turn, int barricade) { if (list.size() > 1) { //至少走过两个格子才能判断是否转弯 int[] ints = list.get(list.size() - 2); //获取路过的倒数第二个格子 if (ints[0] != x && ints[1] != y) { //如果横纵坐标没有相同的,则表示转过弯 turn++; } } list.add(new int[]{x, y}); //走过的格子 if (turn > t) { //转弯次数大于t,则不符合,返回 return 0; } if (newMap[x][y] == '*') { //记录路障的个数 barricade++; } if (barricade > c) { //路障的个数大于c,则不符合,返回 return 0; } if (newMap[x][y] == 'T') { //到达公司完成路程 return 1; } newMap[x][y] = 'X'; //走过的地方记录为X if (x > 0) { //向上 if (newMap[x - 1][y] != 'X') { //走过的格子不再走 if (toCompany(newMap, x - 1, y, list, turn, barricade) == 1) { return 1; } else { newMap[x - 1][y] = map[x - 1][y]; //不符合要求的路程需要恢复 list.remove(list.size() - 1); //走过的格子需要剔除 } } } if (x < n - 1) { //向下 if (newMap[x + 1][y] != 'X') { //走过的格子不再走 if (toCompany(newMap, x + 1, y, list, turn, barricade) == 1) { return 1; } else { newMap[x + 1][y] = map[x + 1][y]; //不符合要求的路程需要恢复 list.remove(list.size() - 1); //走过的格子需要剔除 } } } if (y > 0) { //向左 if (newMap[x][y - 1] != 'X') { //走过的格子不再走 if (toCompany(newMap, x, y - 1, list, turn, barricade) == 1) { return 1; } else { newMap[x][y - 1] = map[x][y - 1]; //不符合要求的路程需要恢复 list.remove(list.size() - 1); //走过的格子需要剔除 } } } if (y < m - 1) { //向右 if (newMap[x][y + 1] != 'X') { //走过的格子不再走 if (toCompany(newMap, x, y + 1, list, turn, barricade) == 1) { return 1; } else { newMap[x][y + 1] = map[x][y + 1]; //不符合要求的路程需要恢复 list.remove(list.size() - 1); //走过的格子需要剔除 } } } return 0; } }
代码实现二:170分代码实现
错误用例:
6 1 1 3 3 T.* *.* *S* YES (答案错误)
9 0 0 2 4 S.*T *… NO (返回非零)
18 没有找到 (答案错误)
package com.codernav.demo.hwod.exam; import java.util.Scanner; /** * @title 上班之路 * @Description Jungle生活在美丽的蓝鲸城,大马路都是方方正正,但是每天马路的封闭情况都不一样。 * 地图由以下元素组成: * 1)"." — 空地,可以达到; * 2)"*" — 路障,不可达到; * 3)"S" — Jungle的家; * 4)"T" — 公司. * 其中我们会限制Jungle拐弯的次数,同时Jungle可以清除给定个数的路障,现在你的任务是计算Jungle是否可以从家里出发到达公司。 * @Author 开发者导航 * @website https://codernav.com * @date 2023/5/28 */ public class Main { static int jR = 0; static int jL = 0; static int gR = 0; static int gL = 0; static int row = 0; static int col = 0; public static void main(String[] args) { Scanner in = new Scanner(System.in); int yW = in.nextInt(); int yZ = in.nextInt(); row = in.nextInt(); col = in.nextInt(); char[][] lu = new char[row][col]; for (int i = 0; i < row; i++) { String str = in.next(); for (int j = 0; j < col; j++) { lu[i][j] = str.charAt(j); if (lu[i][j] == 'S') { jR = i; jL = j; } else if (lu[i][j] == 'T') { gR = i; gL = j; } } } int[][] nWs = new int[row][col]; int[][] nZs = new int[row][col]; boolean[][] states = new boolean[row][col]; if (find(yW, yZ, lu, gR, gL, nWs, nZs, states, 0)) { System.out.println("YES"); } else { System.out.println("NO"); } } public static boolean find(int yW, int yZ, char[][] lu, int nowR, int nowL, int[][] nWs, int[][] nZs, boolean[][] states, int lastFX) { if (0 > nowR || nowR >= nWs.length) { return false; } if (0 > nowL || nowL >= nWs[0].length) { return false; } if (states[nowR][nowL]) { return false; } states[nowR][nowL] = true; char c = lu[nowR][nowL]; if (c == '*') { yZ -= 1; } if (yW < 0 || yZ < 0) { return false; } if ('S' == c) { return true; } int shangR = nowR - 1; int xiaR = nowR + 1; int zuoL = nowL - 1; int youL = nowL + 1; boolean f = false; // 上 int nR = shangR; int nL = nowL; if (2 != lastFX) { if (0 == lastFX || 1 == lastFX) { f = find(yW, yZ, lu, nR, nL, nWs, nZs, states, 1); } else { f = find(yW - 1, yZ, lu, nR, nL, nWs, nZs, states, 1); } } if (f) { return true; } // 下 nR = xiaR; nL = nowL; if (1 != lastFX) { if (0 == lastFX || 2 == lastFX) { f = find(yW, yZ, lu, nR, nL, nWs, nZs, states, 2); } else { f = find(yW - 1, yZ, lu, nR, nL, nWs, nZs, states, 2); } if (f) { return true; } } // 左 nR = nowR; nL = zuoL; if (4 != lastFX) { if (0 == lastFX || 3 == lastFX) { f = find(yW, yZ, lu, nR, nL, nWs, nZs, states, 3); } else { f = find(yW - 1, yZ, lu, nR, nL, nWs, nZs, states, 3); } } if (f) { return true; } // 右 nR = nowR; nL = youL; if (3 != lastFX) { if (0 == lastFX || 4 == lastFX) { f = find(yW, yZ, lu, nR, nL, nWs, nZs, states, 4); } else { f = find(yW - 1, yZ, lu, nR, nL, nWs, nZs, states, 4); } } return f; } }