剑指 Offer 13. 机器人的运动范围

参考：

https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/ji-qi-ren-de-yun-dong-fan-wei-yuan-shi-dfshe-bfszh/
https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/mian-shi-ti-13-ji-qi-ren-de-yun-dong-fan-wei-dfs-b/

深度优先搜索

只需向右和向下两个方向搜索即可

class Solution {
public:

    int k1,m1,n1;
    vector<vector<bool> > board;
    int count=0;
    int movingCount(int m, int n, int k) {
        for(int i=0;i<m;i++)
        {
            vector<bool> temp;
            for(int j=0;j<n;j++)
            {
                temp.push_back(false);
            }
            board.push_back(temp);
        }
        k1=k;m1=m;n1=n;

        dfs(0,0);



        return count;
    }

    bool judge(int i,int j,int k1)
    {
        int sum=0;
        while(i>0)
        {
            sum+=i%10;
            i/=10;
        }
        while(j>0)
        {
            sum+=j%10;
            j/=10;
        }
        if(sum>k1)
            return true;
        else
            return false;
    }

    void dfs(int i,int j)
    {
        if(i>=m1||i<0||j>=n1||j<0||board[i][j]==1||judge(i,j,k1))//最后一个条件判断是否已经走过
        {
            return;
        }

        board[i][j]=true;
        count++;

        //dfs(i-1,j);
        dfs(i+1,j);
        //dfs(i,j-1);
        dfs(i,j+1);



    }
};

剑指 Offer 13. 机器人的运动范围

原文：https://www.cnblogs.com/zchq/p/13789467.html