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. (The number should be printed as an integer whole number eg. if the answer is 10 (its not !!), print out 10, not 10.0 or 10.00 etc)
static class Point { int x, y; Point(int x, int y) { this.x = x; this.y = y; } @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof Point)) return false; Point pair = (Point) o; return x == pair.x && y == pair.y; } @Override public int hashCode() { return 31 * x + y; } } public static int digitSum(int n) { if(n < 0) n = -n; int sum = 0; while(n != 0) { sum += n % 10; n /= 10; } return sum; } 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(); }
Reference:
http://www.careercup.com/question?id=13000687
http://blog.jverkamp.com/2013/08/30/visualizing-the-monkey-grid/
http://stackoverflow.com/questions/18133918/improve-the-solution-to-monkey-grid-puzzle
相关推荐
[图形图像编程精粹].Graphic.Gems.Series1-5,5本电子书+源代码。
Graphics Gems 1-3 合集 跳樓大甩賣啦
[图形图像编程精粹].Graphic.Gems.Series1-5,5本电子书+源代码。
Match 3 Gems Puzzle Game - CoronaSDK 中的 简单 游戏原型_lua_代码_下载
[图形图像编程精粹].Graphic.Gems.Series1-5,5本电子书+源代码。
gems+simics可以模拟sparc处理器的多核功能
官方版本,亲测可用
官方版本,亲测可用
Gems CAP-200-300电容式液位传感器zip,CAP-200 系列方便直接安装于 1/2"NPT 匹配接口,是适用于多种金属和非金属储罐使用的简便液位感测解决方案。高精度传感器由耐用的Delrin? 材料制成,兼有水基和非水基版本。...
Gems CAP-100-200电容式液位传感器zip,CAP-100系列为塑料、玻璃和玻璃纤维等多种瓶状容器提供了独特的液位感测解决方案。非接触式传感器非常适合医疗应用环境,如废弃物、试剂或稀释剂液体,以及深色或粘性液体。...
GPU-GEMS-3D-流体模拟该项目基于GPU Gems 3D流体仿真文章。 本文介绍了一种用于计算和渲染3D流体模拟的方法。 设计用于渲染的方法是为了将流体模拟最好地集成到场景中,并使它与其他场景组件进行交互。 但是,我使用...
sflowtool是一个sflow流量数据收集工具
GPU Gems 1-3 htm格式 高清 文字版
dotGems NFT战斗-电报机器人 安装 git clone ...cd gems.battle-telegram npm install 配置 创建.env文件 BOT_TOKEN= " <@BotFather> " DFUSE_TOKEN= " <PRIVATE> " 快速开始 $ npm start
Game Engine Gems 1-Print
ruby中操作oracle数据库使用的oci8技术相关的gems包,包括3个版本
Gems LS-1微型液位开关zip,该微型液位开关的浮子和杆采用全聚丙烯材料制成,具有广泛的化学兼容性。带凹槽的杆有效阻止固体的堆积。浮球被控制在一体设计的杆滑道内,省去了单独的浮球限位环,同时浮子开关常开/常闭...
这是GPU GEMS文章中有关对Unity进行流体模拟的文章的一部分。 好吧它主要基于上的2D流体模拟。 该项目也基于GPU GEMS文章。 我发现他稍微简化了代码,而且他的处事方式更容易阅读。 每帧有很多阶段要执行,要按正确...
C:/Ruby26/lib/ruby/gems/2.6.0/gems/mimemagic-0.3.10/ext/mimemagic C:/Ruby26/bin/ruby.exe -rrubygems C:/Ruby26/lib/ruby/gems/2.6.0/gems/rake-13.0.6/exe/rake RUBYARCHDIR\=C:/Ruby26/lib/ruby/gems/2.6.0/...
了解有关在Ruby应用程序中需要外部代码库(称为gems)的信息。 了解如何在您的应用程序中使用Bundler和Gemfile管理gem及其依赖项。 定义Ruby 您编写的任何内容都不是100%的代码。 虽然您可能没有注意到它,但是...