【华为面试题】深度优先搜索（一）

- 日理万妓 2023-10-14 18:42 71阅读 0赞

### 题目 ###

Jungle居住在蓝鲸城，一个拥有规则街道的城市。然而，街道每天的封闭情况都是不同的。为了测试Jungle的导航技巧，我们设置了以下挑战：

Jungle必须从他的家（表示为“S”）出发，前往公司（表示为“T”）。  
街道图由以下元素构成:  
“.”: 代表可走的空地。  
“\*”: 代表路障。但Jungle有能力清除一定数量的路障。  
“S”：Jungle的家。  
“T”：公司。  
Jungle的导航能力受到限制：他只能拐一定数量的弯，以及清除一定数量的路障。  
输入

第一行包括两个整数：t 和 c。其中 t 代表Jungle可以拐的弯的数量，c 代表他可以清除的路障的数量。  
第二行包括两个整数：n 和 m，分别代表街道图的行和列数量。  
接下来的 n 行表示街道图，每行包含 m 个字符。

输出

如果Jungle可以成功从家走到公司，则输出"YES"，否则输出"NO"。

### 代码 ###

// 将字符串分割并转换为数字数组
    function splitToNumbers(line) {
        
        return line.split(" ").map(Number);
    }
    
    // 判断是否能够到达目的地
    function canReachEnd(grid, maxTurns, maxBreaks) {
        
        const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]; // 代表四个方向：右、左、下、上
        const rows = grid.length;
        const cols = grid[0].length;
        const seen = Array.from({
         length: rows }, () => Array(cols).fill(false)); // 记录某个点是否已经被访问过
    
        function dfs(x, y, turns, breaks, lastDir) {
        
            // 越界或者当前点已访问，直接返回false
            if (x < 0 || x >= rows || y < 0 || y >= cols || seen[x][y]) return false;
            // 如果当前点就是目的地，返回true
            if (grid[x][y] === 'T') return true;
    
            seen[x][y] = true; // 标记当前点为已访问
            
            // 遍历四个方向
            for (let [dx, dy] of directions) {
        
                let newTurns = turns;
                let newBreaks = breaks;
    
                // 如果换了方向，拐弯次数+1
                if (lastDir && (dx !== lastDir[0] || dy !== lastDir[1])) {
        
                    newTurns++;
                }
    
                // 如果前方有障碍，破壁次数+1
                if (grid[x + dx][y + dy] === '*' ) {
        
                    newBreaks++;
                }
    
                // 递归下一个点
                if (newTurns <= maxTurns && newBreaks <= maxBreaks && dfs(x + dx, y + dy, newTurns, newBreaks, [dx, dy])) {
        
                    return true;
                }
            }
    
            return false;
        }
    
        // 遍历整个网格，找到起始点S并尝试寻路
        for (let i = 0; i < rows; i++) {
        
            for (let j = 0; j < cols; j++) {
        
                if (grid[i][j] === 'S' && dfs(i, j, 0, 0, null)) {
        
                    return "YES";
                }
            }
        }
    
        return "NO";
    }
    
    function solve(inputData) {
        
        const lines = inputData.trim().split('\n');
        const [maxTurns, maxBreaks] = splitToNumbers(lines[0]); // 拐弯次数和破壁次数
        const grid = lines.slice(2); // 获取地图数据
        return canReachEnd(grid, maxTurns, maxBreaks);
    }
    
    const testInput = `
    2 2
    5 5
    S....
    .....
    .....
    .....
    ....T
    `;
    
    console.log(solve(testInput));  // 输出: YES