Pocket Gems 面经题 - Monkey Grid Problem - 我的博客 - ITeye技术网站
There is a monkey which can walk around on a planar grid. The monkey can move one space at a time left, right, up or down. That is, from (x, y) the monkey can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the absolute value of the x coordinate plus the sum of the digits of the absolute value of the y coordinate are lesser than or equal to 19 are accessible to the monkey. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 19. Another example: the point (-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7 = 12, which is less than 19. How many points can the monkey access if it starts at (0, 0), including (0, 0) itself? There is no input for this program.
Print out the how many points can the monkey access.
- private static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
- public static int countPoints(int k) {
- Set<Point> set = new HashSet<>();
- Queue<Point> queue = new LinkedList<>();
- queue.offer(new Point(0, 0));
- while(!queue.isEmpty()) {
- Point p = queue.poll();
- if(set.contains(p) || (digitSum(p.x) + digitSum(p.y)) > k) continue;
- set.add(p);
- for(int i=0; i<4; i++) {
- Point np = new Point(p.x+dir[i][0], p.y+dir[i][1]);
- if(!set.contains(np)) {
- queue.offer(np);
- }
- }
- }
- return set.size();
- }
