题解 | #机器人移动范围#

深度搜索优先算法

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int m = in.nextInt();
            int n = in.nextInt();
            int k = in.nextInt();
            boolean[][] map = new boolean[m][n];
            System.out.print(dfs(map,m,n,0,0,k));
        }
    }

    public static int dfs(boolean[][] map,int m,int n,int M,int N,int k){
        if( M < 0 || N < 0 || M > m-1 || N > n-1 || countSum(M)+countSum(N) > k || map[M][N] ){
            return 0;
        }
        map[M][N] = true;
        return 1+dfs(map,m,n,M+1,N,k)
        +dfs(map,m,n,M,N+1,k)
        +dfs(map,m,n,M-1,N,k)
        +dfs(map,m,n,M,N-1,k);
        
    }

    public static int countSum(int sum){
        int count=0;
        while(sum>0){
            count+=sum%10;
            sum-=(sum%10);
            sum/=10;
        }
        return count;
    }
}