jz13.机器人的运动范围

题目描述

题解

这道题可以参考第十二题的方法, 唯一需要注意的是, 机器人只能在连续的区域运动, 不能跳到其他区域

DFS

public class jz13 {
    int res = 0;
    boolean[][] used;

    public int movingCount(int m, int n, int k) {
        used = new boolean[m][n];
        dfs(0, 0, k, m, n);
        return res;
    }

    private void dfs(int i, int j, int k, int m, int n) {
        if (i < 0 || i >= m || j < 0 || j >= n || used[i][j] || calculate(i) + calculate(j) > k) {
            return;
        }
        used[i][j] = true;
        res++;
        dfs(i + 1, j, k, m, n);
        dfs(i - 1, j, k, m, n);
        dfs(i, j + 1, k, m, n);
        dfs(i, j - 1, k, m, n);
    }

    private int calculate(int x) {
        int ans = 0;
        while (x != 0) {
            ans += x % 10;
            x = x / 10;
        }
        return ans;
    }

}

BFS

public class jz13 {
    int res = 0;
    boolean[][] used;

    public int movingCount(int m, int n, int k) {
        used = new boolean[m][n];
        dfs(0, 0, k, m, n);
        return res;
    }

    private void bfs(int i, int j, int k, int m, int n) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            int x = pos[0];
            int y = pos[1];
            if (x >= 0 && x < m && y >= 0 && y < n && (calculate(x) + calculate(y) <= k) && !used[x][y]) {
                used[x][y] = true;
                res++;
                queue.add(new int[]{x + 1, y});
                queue.add(new int[]{x - 1, y});
                queue.add(new int[]{x, y + 1});
                queue.add(new int[]{x, y - 1});
            }
        }
    }

    private int calculate(int x) {
        int ans = 0;
        while (x != 0) {
            ans += x % 10;
            x = x / 10;
        }
        return ans;
    }

}