华为OD机试真题【上班之路】

1、题目描述

【上班之路】
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个路障，所以无法到达

2、解题思路

首先找到S的位置，再利用回溯算法从S位置开始遍历上、下、左、右四个方向可到达的位置，当到达公司位置T则代表可以到达公司，所有方向都遍历完成都无法到达T则无法到达公司。

3、参考代码

方法一：

import java.util.Scanner;/*** @Author Long* @Date 2023/5/3 20:45*/
public class 上班之路 {private static final int[][] directions = {{0, 1, 1}, {0, -1, 2}, {1, 0, 3}, {-1, 0, 4}};private static int maxTurns, maxClears, rows, cols;private static String[][] matrix;public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNext()) {// 处理输入maxTurns = in.nextInt();maxClears = in.nextInt();rows = in.nextInt();cols = in.nextInt();matrix = new String[rows][cols];char[][] chars = new char[rows][cols];for (int i = 0; i < rows; i++) {String string = in.next();matrix[i] = string.split("");chars[i] = string.toCharArray();}for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {boolean[][] visited = new boolean[cols][rows];if ("S".equals(matrix[i][j])) {if (dfs(visited, i, j, 0, 0, 0)) {System.out.println("YES");return;} else {System.out.println("NO");return;}}}}System.out.println("NO");return;}}public static boolean dfs(boolean[][] visited, int x, int y, int turnsUsed, int clearsUsed, int lastDirection) {if ("T".equals(matrix[x][y])) {return true;}visited[x][y] = true;for (int[] direction : directions) {int curDirection = direction[2];int newX = x + direction[0];int newY = y + direction[1];boolean turnFlag = false;boolean breakFlag = false;if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && !visited[newX][newY]) {if (lastDirection != 0 && lastDirection != curDirection) {if (turnsUsed + 1 > maxTurns) {continue;}turnFlag = true;}if ("*".equals(matrix[newX][newY])) {if (clearsUsed + 1 > maxClears) {continue;}breakFlag = true;}if (dfs(visited, newX, newY, turnsUsed + (turnFlag ? 1: 0), clearsUsed + (breakFlag ? 1 : 0), curDirection)) {return true;}}}return false;}
}

方法二：

import java.util.Scanner;/*** @Author * @Date 2023/5/3 20:45*/
public class 上班之路 {private static final int[][] directions = {{0, 1, 1}, {0, -1, 2}, {1, 0, 3}, {-1, 0, 4}};public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNext()) {// 处理输入int t = in.nextInt();int c = in.nextInt();int n = in.nextInt();int m = in.nextInt();char[][] chars = new char[n][m];for (int i = 0; i < n; i++) {String string = in.next();chars[i] = string.toCharArray();}int sX = 0;int sY = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (chars[i][j] == 'S') {sX = i;sY = j;break;}}if (chars[sX][sY] == 'S') {break;}}boolean[][] used = new boolean[n][m];if (chars[sX][sY] == 'S') {if (dfs(chars, sX, sY, t, c, 0, used)) {System.out.println("YES");} else {System.out.println("NO");}} else {System.out.println("NO");}}}public static boolean dfs(char[][] chars, int x, int y, int t, int c, int dis, boolean[][] used) {int n = chars.length;int m = chars[0].length;if (x < 0 || x >= n || y < 0 || y >= m) {return false;}if (chars[x][y] == 'T') {return true;}used[x][y] = true;for (int i = 0; i < directions.length; i++) {int newX = x + directions[i][0];int newY = y + directions[i][1];// 超过边界if (newX < 0 || newX >= n || newY < 0 || newY >= m || used[newX][newY]) {continue;}if (chars[newX][newY] == '*') {  // 当前是障碍if (c == 0) {  // 清除障碍数用完了continue;}if (dis == 0 || dis == directions[i][2]) {if (dfs(chars, newX, newY, t, c - 1, dis, used)) {return true;}} else {  // 上一步方向跟当前方向不一致if (t == 0) {  // 拐弯数用完continue;}if (dfs(chars, newX, newY, t - 1, c - 1, dis, used)) {return true;}}} else {if (dis == 0 || dis == directions[i][2]) {if (dfs(chars, newX, newY, t, c, dis, used)) {return true;}} else {if (t == 0) {continue;}if (dfs(chars, newX, newY, t - 1, c, dis, used)) {return true;}}}}used[x][y] = false;return false;}}

4、相似题目

（1）西天取经
（2）士兵突击