面试题13: 机器人移动范围

package cn.zxy.interview;

import org.junit.Test;

/**
 * 题目:机器人的运动范围: 地上有一个m行n列的方格。一个机器人从坐标(0, 0)的格子开始移
 * 动，每一次只能往左右上下四个方向移动一格，但是不能进入行坐标和列坐
 * 标的数位之和大于k的格子。请问该机器人能够达到多少个格子？
 *
 * 分析: 到达格子A, 如果A满足条件, 计算可移动的四个方向上每个方向可以到达多少个格子
 * 如果不满足条件, 直接返回
 * 使用递归实现, 进入一个格子, 只要这个格子满足条件, 就可以往下递归
 */

public class A13_RangOfRobot {
    public static int movingCount(int threshold, int rows, int cols){
        int[][] visited = new int[rows][cols];  //记录是否走过
        int count = countCore(0, 0, rows, cols, visited, threshold);
        return count;
    }

    private static int countCore(int i, int j, int rows, int cols, int[][] visited, int threshold) {
        if(i < 0 || i >= rows || j < 0 || j >= cols ||
                numSum(i)+numSum(j) > threshold || visited[i][j] == 1){
            // 该格子不能进入
            return 0;
        }
        // 标记已访问
        visited[i][j] = 1;
        System.out.println("(" + i + "," + j + ")");

        return 1 + countCore(i-1, j, rows, cols, visited, threshold)
                 + countCore(i+1, j, rows, cols, visited, threshold)
                 + countCore(i, j-1, rows, cols, visited, threshold)
                 + countCore(i, j+1, rows, cols, visited, threshold);
    }


    private static int numSum(int num) {
        int sum = 0;
        int temp = num;
        while(temp > 0){
            sum += temp % 10;
            temp /= 10;
        }
        return sum;
    }


    public static void main(String[] args) {
        System.out.println(movingCount(5, 10, 10));
    }
}