https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

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

我的方法一：广度优先搜索BFS

步骤

1. state[m][n]代表一个点遍历的状态，0:未遍历，1:可以达到，2:不能到达
2. 从(0, 0)开始广度优先搜索，使用一个队列q存储未遍历过的点，即状态是0的点
3. 当搜索完后，计算1的点的数量

初始条件

state[m][n]全部初始化为0

边界条件

1. m>0 && n>0& k>=0
2. q先push(0,0)
3. q当为空时，表示已经遍历完

复杂度

时间复杂度：O(MN)
空间复杂度：O(MN)

代码

class Solution {
public:
    int movingCount(int m, int n, int k) {
        if(m<=0 || n<=0 || k<0){
            return 0;
        }

        int** state = new int* [m];
        for(int i = 0; i< m; i++){
            state[i] = new int[n];
            for(int j=0; j<n; j++){
                state[i][j] = 0;
            }
        }

        pair<int, int> location = make_pair(0, 0);//row, col
        queue<pair<int, int>> q;
        q.push(location);
        state[0][0] = 1;

        int next_row = 0;
        int next_col = 0;
        while(!q.empty()){
            location = q.front();
            q.pop();

            {
                //left
                next_row = location.first;
                next_col = location.second - 1;
                walk(m, n, k, next_row, next_col, state, q);
            }
            {
                //right
                next_row = location.first;
                next_col = location.second + 1;
                walk(m, n, k, next_row, next_col, state, q);
            }
            {
                //top
                next_row = location.first - 1;
                next_col = location.second;
                walk(m, n, k, next_row, next_col, state, q);
            }
            {
                //bottom
                next_row = location.first + 1;
                next_col = location.second;
                walk(m, n, k, next_row, next_col, state, q);
            }
        }

        int count = 0;
        for(int i = 0; i< m; i++){
            for(int j=0; j<n; j++){
                if(state[i][j] == 1){
                    count++;
                }
            }
        }
        return count;
    }

    inline void walk(int m, int n, int k, int next_row, int next_col, int** state, queue<pair<int, int>>& q){
        if(next_row >= 0 && next_row<m && next_col>=0 && next_col<n){
            if(state[next_row][next_col] == 0){
                if((next_row/10 + next_row%10 + next_col/10 + next_col%10) <= k){
                    state[next_row][next_col] = 1;
                    q.push(make_pair(next_row, next_col));
                }else{
                    state[next_row][next_col] = 2;
                }
            }
        }
    }
};