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

曾经终败给现在 2023-10-15 11:18 27阅读 0赞

### 题目 ###

现有一个机器人，可放置于M×N的网格中任意位置，每个网格包含一个非负整数编号，当相邻网格的数字编号差值的绝对值小于等于1时，机器人可以在网格间移动。  
问题：求机器人可活动的最大范围对应的网格点数目。说明：网格左上角坐标为(0,0),右下角坐标为(m−1,n−1)。机器人只能在相邻网格间上下左右移动  
输入描述  
第1行输入为M和N，M表示网格的行数N表示网格的列数之后M行表示网格数值，每行N个数值（数值大小用k表示），数值间用单个空格分隔，行首行尾无多余空格M、N、k均为整数，且1≤M,N≤150，0≤k≤50  
输出描述  
输出1行，包含1个数字，表示最大活动区域的网格点数目行首行尾无多余空格  
输入  
4 4  
1 2 5 2  
2 4 4 5  
3 5 7 1  
4 6 2 4  
输出  
6

### 解题思路 ###

对于每个网格点，执行深度优先搜索。使用visited数组来记录已经访问过的网格点。对于当前网格点，遍历其上下左右四个相邻网格点，如果相邻网格点未被访问且数值差值的绝对值小于等于1，则将count加1，并继续遍历相邻网格点。

### 代码 ###

// 定义四个方向，上下左右
    let directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    
    function maxMovableArea() {
        
        // 测试样例
        let grid = [
            [1, 2, 5, 2],
            [2, 4, 4, 5],
            [3, 5, 7, 1],
            [4, 6, 2, 4]
        ];
        let rows = grid.length;
        let cols = grid[0].length;
        // 定义一个变量记录最大区域
        let maxArea = 0;
    
        // 深度优先搜索
        function dfs(row, col, visited) {
        
            // 如果出界或者已经访问过，则返回0
            if (row < 0 || row >= rows || col < 0 || col >= cols || visited[row][col]) {
        
                return 0;
            }
            
            // 当前单元格的值
            let currentCell = grid[row][col];
            // 标记当前单元格已访问
            visited[row][col] = true;
    
            // 至少有一个单元格（当前单元格）
            let count = 1;  
            // 遍历四个方向
            for (let direction of directions) {
        
                let newRow = row + direction[0];
                let newCol = col + direction[1];
                
                // 检查新的位置是否有效
                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && !visited[newRow][newCol]) {
        
                    // 检查新位置与当前位置的数值差值是否不大于1
                    if (Math.abs(currentCell - grid[newRow][newCol]) <= 1) {
        
                        count += dfs(newRow, newCol, visited);
                    }
                }
            }
    
            // 返回搜索到的区域大小
            return count;
        }
    
        // 遍历所有单元格，从每一个单元格开始搜索
        for (let i = 0; i < rows; i++) {
        
            for (let j = 0; j < cols; j++) {
        
                // 初始化一个二维数组记录哪些单元格已被访问
                let visited = Array(rows).fill(false).map(() => Array(cols).fill(false));
                // 更新最大区域大小
                maxArea = Math.max(maxArea, dfs(i, j, visited));
            }
        }
    
        // 返回最大区域大小
        return maxArea;
    }
    
    
    console.log(maxMovableArea());