[LC]13. 机器人的运动范围

🚩传送门：力扣题目
力扣题目

题目

地上有一个行列的方格，从坐标 到坐标 。一个机器人从坐标 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于的格子。
例如，当为时，机器人能够进入方格 ，因为。但它不能进入方格，因为。请问该机器人能够到达多少个格子？

示例 1

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

解题思路：DFS

本问题是典型的搜索问题，可使用 深度优先搜索（DFS） 解决。

复杂度分析

时间复杂度： ，其中 为递归深度，最差情况 。

空间复杂度： ，其中 为递归深度。

我的代码

class Solution {
    int count;
    public int movingCount(int m, int n, int k) {
        count = 0;
        boolean[][] view = new boolean[m][n];
        dfs(0, 0, m, n, k, view);
        return count;
    }
    private void dfs(int i, int j, int m, int n, int k, boolean[][] view) {
        if (isvalid(i, j, m, n, k, view)) {
            // 当前位置可到
            count++;
            view[i][j] = true;
            int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            // 四向搜索
            for (int l = 0; l < dir.length; l++) {
                dfs(i + dir[l][0], j + dir[l][1], m, n, k, view);
            }
        }
    }
    private boolean isvalid(int i, int j, int m, int n, int k, boolean[][] view) {
        // 越界
        if (i < 0 || i >= m || j < 0 || j >= n) return false;
        // 已经访问过,防止走回头路
        if (view[i][j]) return false;
        // 值超过了
        int sum = 0;
        while (i != 0) {
            sum += i % 10;
            i /= 10;
        }
        while (j != 0) {
            sum += j % 10;
            j /= 10;
        }
        if (sum > k) return false;
        return true;
    }
}