medium 剑指 Offer 机器人的运动范围 DFS（递归）广度优先遍历 BFS（队列）

medium 剑指 Offer 机器人的运动范围 DFS（递归）广度优先遍历 BFS（队列）

---

深度优先遍历 DFS（递归）： c++

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector> visited(m, vector(n, 0));  // m个vector
        int ans = search(0, 0, m, n, k, visited);

        return ans;
    }

private:
    int digit_sum(int i){
        int sum = 0;
        while(i>0){
            sum += i%10;
            i /= 10;
        }
        return sum;
    }

    int search(int i, int j, int m, int n, int k, vector>& visited){
        // 递归出口1: 上下左右出界; 数位之和大于k; 访问过
        if(i<0 || i>=m || j<0 || j>=n || (digit_sum(i)+digit_sum(j)) > k || visited[i][j]==true){
            return 0;
        } 

        // 可以继续递归
        visited[i][j] = true;

        return 1 + search(i, j+1, m, n, k, visited) + search(i+1, j, m, n, k, visited);
    }

};

python

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def digit_sum(i):
            sum = 0
            while i>0:
                sum += i%10;
                i //= 10;

            return sum;     

        def search(i, j, visited):
            # 递归出口1: 上下左右出界; 数位之和大于k; 访问过
            if i<0 or i>=m or j<0 or j>=n or (digit_sum(i)+digit_sum(j)) > k or visited[i][j]==True:
                return 0

            # 可以继续递归
            visited[i][j] = True;

            return 1 + search(i, j+1, visited) + search(i+1, j,visited); 

        visited = [[0] * n for _ in range(m)]   # m个[0][0]...[0](长度为n)的矩阵
        ans = search(0, 0, visited);

        return ans;

---

广度优先遍历 BFS（队列）： c++

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector> visited(m, vector(n, 0));
        queue> que;  // 队列里放vector{},{}里放int
        que.push({0, 0});  // 初始访问坐标(0, 0)
        int ans = 0;

        while(!que.empty()){
            vector x = que.front();
            que.pop();
            int i = x[0], j = x[1];
            if(i<0 || i>=m || j<0 || j>=n || (digit_sum(i)+digit_sum(j)) > k || visited[i][j]==true){
                continue;  // 不符合条件, 跳出while这一次循环, 不加入他的分支
            } 
            // 符合条件,标记访问过,并加入他的分支
            visited[i][j] = true;
            ans++;
            que.push({i, j+1});  // 向右搜索
            que.push({i+1, j});  // 向下搜索
        }

        return ans;
    }

private:
    int digit_sum(int i){
        int sum = 0;
        while(i>0){
            sum += i%10;
            i /= 10;
        }
        return sum;
    }    

};

python

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def digit_sum(i):
            sum = 0
            while i>0:
                sum += i%10;
                i //= 10;

            return sum; 

        que = collections.deque([(0, 0)])   # 创建python双端队列，并放入初始访问位置(i,j)
        visited = [[0] * n for _ in range(m)]   # m个[0][0]...[0](长度为n)的矩阵 
        ans = 0 

        while que:
            x = que.popleft()  # 返回并删除队列顶端元素
            i = x[0]
            j = x[-1]
            if i<0 or i>=m or j<0 or j>=n or (digit_sum(i)+digit_sum(j)) > k or visited[i][j]==True:
                continue

            # 可以继续加入队列 append
            visited[i][j] = True
            ans += 1
            que.append((i,j+1))  # 注意append格式 ()
            que.append((i+1,j))

        return ans;

---