描述

这是一篇针对初学者的题解。共用两种方法解决，
知识点：DFS，BFS
难度：二星

题解

题目描述：给定一个矩阵的行和列row，col和阈值sho，从(0,0)出发，每次可以往上下左右四个方向走，并且走到(i,j)时，i和j的每位数之和需要小于等于sho，问最多可以走多少格子。

方法一：DFS遍历

根据题目描述，我们可以模拟题目，我们假设一个5x5矩阵，阈值sho=3，如果我们用DFS的话，就相当于“不撞南墙不回头”，我在下面画了一个图，
最开始，我们在(0,0)的位置，我们假设按照{右，下，左，上}的方向去试探。所以我们走的顺序应该是按照图中的下标走的。
当走到4的时候，发现不能往继续往右边走，并且4个方向都走不通了，那就回溯到3,发现可以走到5，接着就站在5的视角，发现可以走6，就一直按照这个想法。

本题的递归函数就是：首先站在(0,0)的视角，先往右试探，发现可以走，就以下一个为视角，继续做相同的事情。
递归函数模板为：

dfs(){

    // 第一步，检查下标

    // 第二步：检查是否被访问过，或者是否满足当前匹配条件

    // 第三步：检查是否满足返回结果条件

    // 第四步：都没有返回，说明应该进行下一步递归
    // 标记
    dfs(下一次)
    // 回溯
}  
int main() {
    dfs(0, 0);
}

按照模板改写代码：

class Solution {

public:
    using V = vector<int>;
    using VV = vector<V>;    
    int dir[5] = {-1, 0, 1, 0, -1};

    int check(int n) {
        int sum = 0;

        while (n) {
            sum += (n % 10);
            n /= 10;
        }

        return sum;
    }

    void dfs(int x, int y, int sho, int r, int c, int &ret, VV &mark) {
        // 检查下标 和 是否访问
        if (x < 0 || x >= r || y < 0 || y >= c || mark[x][y] == 1) {
            return;
        }
        // 检查当前坐标是否满足条件
        if (check(x) + check(y) > sho) {
            return;
        }
        // 代码走到这里，说明当前坐标符合条件
        mark[x][y] = 1;
        ret += 1;

        for (int i = 0; i < 4; ++i) {
            dfs(x + dir[i], y + dir[i + 1], sho, r, c, ret, mark);
        }



    } 
    int movingCount(int sho, int rows, int cols)
    {
        if (sho <= 0) {
            return 0;
        }

        VV mark(rows, V(cols, -1));
        int ret = 0;
        dfs(0, 0, sho, rows, cols, ret, mark);
        return ret;
    }
};

时间复杂度：O(mn)， m,n为矩阵大小，每个元素最多访问过一次
空间复杂度：O(mn)

方法二：BFS遍历

当前图的遍历算法还有bBFS，所以也可以用BFS做。方法一实例的图，用BFS就是如下这样：

代码如下：

class Solution {
public:
    using pii = pair<int,int>;
    int dir[5] = {-1, 0, 1, 0, -1};
    int check(int n) {
        int sum = 0;

        while (n) {
            sum += (n % 10);
            n /= 10;
        }

        return sum;
    }
    int movingCount(int sho, int rows, int cols)
    {
        if (sho <= 0) {
            return 0;
        }

        int ret = 0;
        int mark[rows][cols];
        memset(mark, -1, sizeof(mark));
        queue<pii> q;
        q.push({0, 0});
        mark[0][0] = 1;


        while (!q.empty()) {
            auto node = q.front();
            q.pop();
            // 每次保证进队列的都是满足条件的坐标
            ++ret;

            for (int i = 0; i < 4; ++i) {
                int x = node.first + dir[i];
                int y = node.second + dir[i + 1];

                if (x >= 0 && x < rows && y >= 0 && y < cols && mark[x][y] == -1) {
                    if (check(x) + check(y) <= sho) {
                        q.push({x, y});
                        mark[x][y] = 1;
                    }
                }
            }
        }

        return ret;
    }
};

时间复杂度：O(mn)， m,n为矩阵大小，每个元素最多访问过一次
空间复杂度：O(mn)