当前位置：首页 > 牛客 > 牛客25438题解析：机器人移动可达点数量的BFS算法优化

牛客25438题解析：机器人移动可达点数量的BFS算法优化

2天前

一、题目解读

牛客25438题要求计算在一个m行n列的网格中，从原点(0,0)出发，每次只能向上、下、左、右移动一步，且移动后的坐标各位数字之和不超过k的情况下，可达点的总数。题目考察对BFS（广度优先搜索）算法的应用，以及数字各位和的计算与边界条件的判断。

二、解题思路

采用BFS算法，通过队列存储待遍历的节点，并配合方向数组实现四方向移动。关键在于设计两个核心函数：

1. digitSum函数：通过循环取余和整除逐位拆解数字，计算各位之和。

2. isValid函数：综合判断坐标合法性（越界、数字和超限、是否已访问）。

主逻辑通过BFS从原点开始，遍历所有可达点并标记，最终统计总数量。

三、解题步骤

1. 预处理与初始化：输入m、n、k，创建visited矩阵标记访问状态，队列初始化原点。

2. BFS循环：

○ 取出队首节点，遍历四个方向偏移。

○ 调用isValid判断新坐标合法性，若合法则标记visited并入队，同时计数+1。

3. 终止条件：队列为空时结束，返回总计数。

四、代码和注释

#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;
}

代码注释说明：

● 主函数movingCount中，先判断输入合法性，避免无效参数导致错误。

● 使用方向数组dx、dy简化四方向偏移计算，提升代码可读性。

● 通过visited矩阵避免重复遍历，保证BFS正确性。