leetcode-机器人的运动范围

刷leetcode《剑指offer》中第十三题"机器人的运动范围",以下记录一下解题思路

题目

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

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

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

解析

1. 与第十二题十分类似，只是这道题可以选择四个方向走，并且越界条件不一样
2. 因为可以选择四个方向的，所以可以使用深度DFS遍历算法以及广度BFS遍历算法

注意

1. 因为题目是从左上角[0,0]处进行走，所以可以不考虑向上走以及向左走，节约空间和时间
2. 需要标记所走的位置为true，不能回头走
3. 题目要求m,n>=100,K<=20,分解数字的时候可以直接求/和求%
4. DFS以及BFS对比，如下:

具体代码实现

方法一：深度DFS遍历算法

class Solution {
    /**
     * 示例 1：
     * 输入：m = 2, n = 3, k = 1
     * 输出：3
     * @param m 行
     * @param n 列
     * @param k 目标值
     * @return 能到达的格子数
     */
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return dfs(0, 0, m, n, k, visited);
    }

    private int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
        // 计算target
        int target = i % 10 + i / 10 + j % 10 + j / 10;
        // 判断越界条件
        if (i >= m || j >= n || k < target || visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, m, n, k, visited) + dfs(i, j + 1, m, n, k, visited);
    }
}

方法二：广度BFS遍历算法

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return bfs(m, n, k, visited);
    }

    private static int bfs(int m, int n, int k, boolean[][] visited) {
        int flag = 0;
        // 使用队列保存格子坐标，二维数组
        Queue<int[]> queue = new LinkedList<>();
        // 把坐标点添加到队列中
        queue.add(new int[]{0, 0});
        while (queue.size() > 0) {
            // 移除头部元素
            int [] x = queue.poll();
            // 先进先出，尾部添加元素，头部移除元素
            int i = x[0],j = x[1];
            // 计算target
            int target = i % 10 + i / 10 + j % 10 + j / 10;
            // 边界条件判断
            if (i >= m || j >= n || k < target || visited[i][j]){
                continue;
            }
            visited[i][j] = true;
            flag++;
            // 向右走
            queue.add(new int[]{i+1,j});
            // 向下走
            queue.add(new int[]{i,j+1});
        }
        return flag;
    }
}