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

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

题目来源：https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof

输入：m = 2, n = 3, k = 1
输出：3

输入：m = 3, n = 1, k = 0
输出：1

1 <= n,m <= 100
0 <= k <= 20

class Solution {


  public int movingCount(int m, int n, int k) {

    /**
     * 二维数组，记录元素是否被已被访问
     */
    boolean[][] visited = new boolean[m][n];

    // 从 (0, 0) 点开始进行 dfs 操作，从上、下、左、右4个方向递归调用
    return this.dsf(visited, m, n, 0, 0, k);
  }

  private int dsf(boolean[][] visited, int row, int col, int i, int j, int k) {
    /**
     * 终止条件：1、数组越界 2、数据已被访问过 3、当前字符与期望的字符不符合 4、或者访问受限（数值加起来为k）
     */
    if (i < 0 || i >= row || j < 0 || j >= col || visited[i][j] || isAccessDenied(i, j, k)) {
      return 0;
    }

    visited[i][j] = true;
    return 1+ dsf(visited, row, col, i + 1, j, k) + dsf(visited, row, col, i - 1, j, k)
        + dsf(visited, row, col, i, j + 1, k) + dsf(visited, row, col, i, j - 1, k);
  }

  private boolean isAccessDenied(int i, int j, int k) {
    /**
     * 不能进入行坐标和列坐标的数位之和大于k的格子。
     * 例如，当k为18时，机器人能够进入方格 [35, 37] ，
     * 因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19
     * 
     * 另外：
     * 1 <= n,m <= 100 
     * 
     * 所以下标范围为0-99，只要考虑2位数即可
     */
    int sum = i / 10 + i % 10 + j / 10 + j % 10;
    return sum > k;
  }

}

class Solution {


  public int movingCount(int m, int n, int k) {

    /**
     * 二维数组，记录元素是否被已被访问
     */
    boolean[][] visited = new boolean[m][n];

    // 从 (0, 0) 点开始进行 dfs 操作，从上、下、左、右4个方向递归调用
    return this.dsf(visited, m, n, 0, 0, k);
  }

  private int dsf(boolean[][] visited, int row, int col, int i, int j, int k) {
    /**
     * 终止条件：1、数组越界 2、数据已被访问过 3、当前字符与期望的字符不符合 4、或者访问受限（数值加起来为k）
     */
    if (i < 0 || i >= row || j < 0 || j >= col || visited[i][j] || isAccessDenied(i, j, k)) {
      return 0;
    }

    visited[i][j] = true;

    return 1+ dsf(visited, row, col, i + 1, j, k) 
         + dsf(visited, row, col, i, j + 1, k) ;
  }

  private boolean isAccessDenied(int i, int j, int k) {
    /**
     * 不能进入行坐标和列坐标的数位之和大于k的格子。
     * 例如，当k为18时，机器人能够进入方格 [35, 37] ，
     * 因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19
     * 
     * 另外：
     * 1 <= n,m <= 100 
     * 
     * 所以下标范围为0-99，只要考虑2位数即可
     */
    int sum = i / 10 + i % 10 + j / 10 + j % 10;
    return sum > k;
  }

}