【14】 DFS 机器人活动范围 （static插曲）

题目

地上有一个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。请问该机器人能够到达多少个格子？

思路

一开始没想到思路，后来想，不就是有障碍的DFS吗？以后看到这类题，一定要想到DFS！！！:"到达……多少……”

有一个奇怪的地方，这个代码我在IDEA上跑相同的参数，和leetcode跑出来的不一样？？？

小插曲：

刚写完代码，我在IDEA里跑相同的test都没问题啊，但怎么LT跑不了？？？？？后来发现是我敲代码的时候吧ans声明为static了……

代码：

class Solution {
    /
    public int ans=0;
    //vis初始为false 若为true代表访问且不通过
    public int movingCount(int m, int n, int k) {
        boolean[][] vis = new boolean[m][n];
        if(k==0) return 1;
        dfs(k,0,0,m,n,vis);
        // for(int i=0;i<m;i++){
        //     for(int j=0;j<n;j++){
        //         dfs(k,i,j,m,n,vis);
        //     }
        // }
        return ans;
    }

    public void dfs(int k,int r,int c,int m,int n,boolean[][] vis){
        if(r<0||c<0||r>m-1||c>n-1||vis[r][c]) return ;
        else if(isGreater(k,r,c)!=true){
            return ;
        }
        else{
            vis[r][c]=true;
            //正常流程
            ans++;
            dfs(k,r+1,c,m,n,vis);
            dfs(k,r,c+1,m,n,vis);
            dfs(k,r-1,c,m,n,vis);
            dfs(k,r,c-1,m,n,vis);
        }

    }
    //if k>=(r,c) return true
    public boolean isGreater(int k,int r,int c){
        int rt = r/10;r=r%10;
        int ct =c/10;c=c%10;
        return k>=(rt+r+ct+c);
    }
}

【14】 DFS 机器人活动范围 （static插曲）

原文：https://www.cnblogs.com/Jun10ng/p/12359292.html