`

Pocket Gems 面经题 - Monkey Grid Problem

 
阅读更多

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

分享到:
评论

相关推荐

    Graphics Gems[1-3]

    《Graphics Gems[1-3]》是一套经典的计算机图形学著作集合,包含了丰富的图形处理算法和技术。这套合集由三个部分组成,分别是《Graphics Gems 1》、《Graphics Gems 2》和《Graphics Gems 3》,是图形学领域的重要...

    gems-release-2.0

    在标题“gems-release-2.0”中,我们看到的是GEMS的一个特定版本——2.0,这代表了该软件的一次重大更新,可能包含了性能提升、新功能的添加以及对已有功能的优化。 Simics是一款由Intel开发的全系统仿真平台,它...

    [图形图像编程精粹].Graphic.Gems.Series1-5.part2.rar

    [图形图像编程精粹].Graphic.Gems.Series1-5,5本电子书+源代码。

    [图形图像编程精粹].Graphic.Gems.Series1-5.part1

    [图形图像编程精粹].Graphic.Gems.Series1-5,5本电子书+源代码。

    [图形图像编程精粹].Graphic.Gems.Series1-5.part3.rar

    [图形图像编程精粹].Graphic.Gems.Series1-5,5本电子书+源代码。

    Match 3 Gems Puzzle Game - CoronaSDK 中的 简单 游戏原型_lua_代码_下载

    项目文件"Match-3-Gems-Puzzle-Game-master"包含以下几个主要部分: - `main.lua`: 游戏的主入口文件,包含了游戏的初始化、更新和事件处理。 - `game.lua`: 游戏逻辑的核心模块,包括匹配检查、消除处理和分数计算...

    apa-gems-1.1-sources.jar

    官方版本,亲测可用

    apa-gems-1.0-sources.jar

    官方版本,亲测可用

    Gems CAP-200-300电容式液位传感器.zip

    Gems CAP-200-300电容式液位传感器zip,CAP-200 系列方便直接安装于 1/2"NPT 匹配接口,是适用于多种金属和非金属储罐使用的简便液位感测解决方案。高精度传感器由耐用的Delrin? 材料制成,兼有水基和非水基版本。...

    Gems CAP-100-200电容式液位传感器.zip

    Gems CAP-100-200电容式液位传感器zip,CAP-100系列为塑料、玻璃和玻璃纤维等多种瓶状容器提供了独特的液位感测解决方案。非接触式传感器非常适合医疗应用环境,如废弃物、试剂或稀释剂液体,以及深色或粘性液体。...

    GPU-GEMS-3D-Fluid-Simulation:Unity中的3D流体模拟

    GPU-GEMS-3D-流体模拟该项目基于GPU Gems 3D流体仿真文章。 本文介绍了一种用于计算和渲染3D流体模拟的方法。 设计用于渲染的方法是为了将流体模拟最好地集成到场景中,并使它与其他场景组件进行交互。 但是,我使用...

    gems.battle-telegram:dotGems NFT Battle-Telegram机器人

    dotGems NFT战斗-电报机器人 安装 git clone ...cd gems.battle-telegram npm install 配置 创建.env文件 BOT_TOKEN= " &lt;@BotFather&gt; " DFUSE_TOKEN= " &lt;PRIVATE&gt; " 快速开始 $ npm start

    GPU Gems 1-3

    《GPU Gems 1-3》是一套集合了GPU编程领域先进技术与实践经验的系列书籍,包含了丰富的图形处理单元(GPU)编程知识。这个压缩包包含了htm格式的高清文字版,适合程序员们在线阅读或离线查阅。标签“GPU Gems1 Gems2...

    hello-ruby-gems-happy-birthday:宝石说生日快乐

    标题中的“hello-ruby-gems-happy-birthday”是一个基于Ruby的Gem项目,它的主要功能是祝贺生日。这个Gem的名字“happy-birthday”表明它是一个简单的程序,可以在命令行上运行,用来庆祝生日。 Ruby是一种面向对象...

    Graphics Gems I-III

    《Graphics Gems I-III》是一套非常经典的图形学著作,由多个独立的章节组成,涵盖了图形学几何算法、渲染技术等多个重要领域。这套书籍的每一卷都汇集了业界专家和学者的经验分享,提供了大量实用的代码和算法实现...

    ruby-oracle相关的数据库操作的gems包

    标题提到的"ruby-oracle相关的数据库操作的gems包"是指一组用于连接和交互Oracle数据库的Ruby库。描述中指出,这些包主要基于oci8技术,oci8是Oracle公司提供的一个C接口,允许其他编程语言,如Ruby,与Oracle数据库...

    Gems CT-1000电位式液位计.zip

    **Gems CT-1000电位式液位计** Gems CT-1000电位式液位计是一款专为连续填充液位及界面测量而设计的精密仪器,广泛应用于各种电导液体的测量场景。这款液位计以其高精度和出色的稳定性,在工业领域中得到了广泛应用...

    sflowtool-sflow流量数据收集工具

    **正文** sflowtool是一款强大的网络流量分析工具,专门用于收集和解析sFlow协议生成的流量数据。sFlow是一种在交换机、路由器等网络设备上实施的流量采样技术,它能够提供网络流量的实时监控和性能分析。...

    GeMS++-开源

    "GeMS++-开源" 这个标题揭示了我们正在讨论的是一款名为 GeMS++ 的开源软件项目。"开源" 指的是该软件的源代码是公开的,允许用户查看、使用、修改和分发,遵循特定的开源许可证。 **描述解读:** 描述中提到,...

    Gems LS-1微型液位开关.zip

    Gems LS-1微型液位开关zip,该微型液位开关的浮子和杆采用全聚丙烯材料制成,具有广泛的化学兼容性。带凹槽的杆有效阻止固体的堆积。浮球被控制在一体设计的杆滑道内,省去了单独的浮球限位环,同时浮子开关常开/常闭...

Global site tag (gtag.js) - Google Analytics