题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

题解——BFS（广度优先搜索）

<图像来源于极客时间课程——数据结构与算法之美。侵权请联系删除，欢迎订阅>

int get_sum(int row, int col) {
    int ans = 0;
    while (row || col) {
        ans = ans + row % 10 + col % 10;
        row = row / 10;
        col = col / 10;
    }
    return ans;
}

int BFS(int threshold, int rows, int cols) {
    int ans = 0;
    if (threshold <= 0) return ans;
    // 使用队列保存待验证节点，使用二维向量保存访问过的节点
    vector<vector<bool> > visited(rows, vector<bool>(cols, false));
    queue<int> my_queue;

    my_queue.push(0);
    visited[0][0] = true;
    // 队列不为空 持续判定
    while (!my_queue.empty()) {
        // 获取队头节点在数组中的位置
        int row = my_queue.front() / cols;
        int col = my_queue.front() % cols;
        if (get_sum(row, col) <= threshold) {
            // 满足要求则可达位置数加1，并将相邻左、下节点入队
            ans++;
            if (row != rows - 1 && !visited[row + 1][col]) {
                my_queue.push((row + 1) * cols + col);
                visited[row + 1][col] = true;
            }
            if (col != cols - 1 && !visited[row][col + 1]) {
                my_queue.push(row * cols + col + 1);
                visited[row][col + 1] = true;
            }
        }
        // 弹出队头节点
        my_queue.pop();
    }
    return ans;
}

题解——DFS（深度优先搜索）

深度优先搜索，代码思路：将起始节点入队，然后循环判断队列是否为空，不为空则检测队头节点是否符合要求，如果符合，则可达位置数加1，并将该节点的上、下、左、右节点入队，并弹出队头节点；不符合要求，同样将队头节点弹出。

图像来源于极客时间课程——数据结构与算法之美。侵权请联系删除，欢迎订阅

int DFS(int threshold, int rows, int cols) {
    int ans = 0;
    if (threshold <= 0) return ans;

    vector<vector<bool> > visited(rows, vector<bool>(cols, false));
    queue<int> my_queue;

    my_queue.push(0);
    visited[0][0] = true;
    while (!my_queue.empty()) {
        int row = my_queue.front() / cols;
        int col = my_queue.front() % cols;
        if (get_sum(row, col) <= threshold) {
            ans++;
            // top
            if (row != 0 && !visited[row - 1][col]) {
                my_queue.push((row - 1) * cols + col);
                visited[row - 1][col] = true;
            }
            // down
            if (row != rows - 1 && !visited[row + 1][col]) {
                my_queue.push((row + 1) * cols + col);
                visited[row + 1][col] = true;
            }
            // left
            if (col != 0 && !visited[row][col - 1]) {
                my_queue.push(row * cols + col + 1);
                visited[row][col - 1] = true;
            }
            // right
            if (col != cols - 1 && !visited[row][col + 1]) {
                my_queue.push(row * cols + col + 1);
                visited[row][col + 1] = true;
            }
        }
        my_queue.pop();
    }
    return ans;
}