牛客网25438题：BFS算法解机器人移动范围问题

一、题目解读

题目要求计算机器人从m×n网格的(0,0)出发，可到达的格子数量。移动规则：每次只能向上下左右移动，且目标位置的数位和不超过给定阈值k。例如当k=8时，(35,37)的数位和3+5+3+7=18>8不可达。这是典型的图遍历问题，适合用BFS/DFS解决。

二、解题思路

1. 数位和计算：通过digitSum函数分解数字各位相加

2. 合法性校验：isValid函数综合判断坐标边界、访问状态和数位和阈值

3. BFS核心逻辑：

• 使用队列实现广度优先遍历

• 从(0,0)出发，标记已访问

• 每次扩展四个方向的相邻格子

• 合法则加入队列并计数

三、解题步骤

1. 初始化visited矩阵和计数变量

2. 将起点(0,0)入队并标记

3. 循环处理队列直到为空：

• 取出队首元素

• 检查四个移动方向的新坐标

• 若坐标合法则标记访问并入队

4. 返回最终的计数结果

四、完整代码实现

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 计算数字各位之和
int digitSum(int num) {
    int sum = 0;
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

// 检查坐标是否合法
bool isValid(int x, int y, int m, int n, int k, vector<vector<bool>>& visited) {
    return x >= 0 && x < m && y >= 0 && y < n && 
           (digitSum(x) + digitSum(y)) <= k && 
           !visited[x][y];
}

int movingCount(int m, int n, int k) {
    if (m <= 0 || n <= 0 || k < 0) return 0;
    
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    queue<pair<int, int>> q;
    int count = 0;
    
    // 初始位置(0,0)
    q.push({0, 0});
    visited[0][0] = true;
    count++;
    
    // 四个移动方向
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    
    while (!q.empty()) {
        auto curr = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = curr.first + dx[i];
            int ny = curr.second + dy[i];
            
            if (isValid(nx, ny, m, n, k, visited)) {
                visited[nx][ny] = true;
                q.push({nx, ny});
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    int m, n, k;
    cin >> m >> n >> k;
    cout << movingCount(m, n, k) << endl;
    return 0;
}

五、总结

本题通过BFS实现了高效的网格遍历，关键在于：

1. 数位和计算的优化处理

2. 使用visited矩阵避免重复计算

3. 队列数据结构确保广度优先顺序 算法时间复杂度O(mn)，空间复杂度O(mn)，适合处理中等规模网格问题。