题目:https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
代码:
class Solution { public int movingCount(int m, int n, int k) { LinkedList<Point> queue = new LinkedList<>(); int[][] visited = new int[m][n]; queue.offerLast(new Point(0, 0)); visited[0][0] = 1; int count = 0; Point p; while(!queue.isEmpty()){ p = queue.pollFirst(); count ++; if(p.x + 1 < m && visited[p.x + 1][p.y] == 0 && check(p.x+1, p.y, k)){ queue.offerLast(new Point(p.x+1, p.y)); visited[p.x+1][p.y] = 1; } if(p.y+1 < n && visited[p.x][p.y + 1] == 0 && check(p.x, p.y+1, k)){ queue.offerLast(new Point(p.x, p.y+1)); visited[p.x][p.y+1] = 1; } } return count; } private boolean check(int x, int y, int k){ int sum = 0; while(x > 0){ sum += x % 10; x /= 10; } while(y > 0){ sum += y % 10; y /= 10; } return sum <= k; } class Point{ int x, y; public Point(int x, int y){ this.x = x; this.y = y;} } }
执行用时:4 ms, 在所有 Java 提交中击败了26.55%的用户
内存消耗:36.2 MB, 在所有 Java 提交中击败了23.34%的用户优化:上面方法中,机器人每走一步都要判断该步是否符合条件(调用ckeck方法),但实际上每一步都只移动一个方向,这样不需要每次都重新计算纵方向和横方向的各个位数之和。
class Solution { public int movingCount(int m, int n, int k) { LinkedList<Point> queue = new LinkedList<>(); int[][] visited = new int[m][n]; queue.offerLast(new Point(0, 0, 0, 0)); visited[0][0] = 1; int count = 0; Point p; while(!queue.isEmpty()){ p = queue.pollFirst(); count ++; if(p.x + 1 < m && visited[p.x + 1][p.y] == 0){ int t = p.x % 10 == 9 ? p.xSum - 8 : p.xSum + 1; if(t + p.ySum <= k){ queue.offerLast(new Point(p.x+1, p.y, t, p.ySum)); visited[p.x+1][p.y] = 1; } } if(p.y + 1 < n && visited[p.x][p.y + 1] == 0){ int t = p.y % 10 == 9 ? p.ySum - 8 : p.ySum + 1; if(t + p.xSum <= k){ queue.offerLast(new Point(p.x, p.y+1, p.xSum, t)); visited[p.x][p.y+1] = 1; } } } return count; } class Point{ int x, y; int xSum, ySum; public Point(int x, int y, int xSum, int ySum){ this.x = x; this.y = y; this.xSum = xSum; this.ySum = ySum; } } }执行用时:3 ms, 在所有 Java 提交中击败了30.20%的用户 内存消耗:36.1 MB, 在所有 Java 提交中击败了26.73%的用户