[八我司] Expedia一年半遊:这是一個特別適合養老待退的地方

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 3485|回复: 10
收起左侧

[找工就业] Epic OA 的jumper game

[复制链接] |试试Instant~ |关注本帖
我的人缘0
davidzeng1990 发表于 2014-11-16 04:24:22 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

2015(10-12月)-[12]CS硕士+fresh grad 无实习/全职 - 内推| 码农类General其他@Epic

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
Jumper Game: A NxN grid which contains either of 0-empty, 1 - player1, 2 - player 2. Given a position in the grid, find the longest jump path. For jump path, you can horizontally or vertically, you can jump on opponent cell and also the landing cell should be empty. No opponent cell can be jumped more than once. Write a function which takes grid and a specific position in the grid, and returns the longest possible number of jumps in the grid.


各位大神,求这道题的解法,C++最好,java也可以。。。明天OA了,只能伸手了。。。求各位大神帮下忙。。。。。

上一篇:求Pure Storage onsite面经
下一篇:求问Epic OA 新语言学习具体是什么样的?
我的人缘0
Adeath 发表于 2014-11-16 05:16:43 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
  1. int maxLen (int x, int y){
  2.             int leftLen = 0;
    -google 1point3acres
  3.             if (x-2>=0 && board[x-2][y]==0 && board[x-1][y]==2 && !jumped[x-1][y]){
  4.                     // left is an opposite and left-1 is empty and not jumped, jump left
  5.                     jumped[x-1][y] = true;. 1point 3acres 论坛
  6.                     leftLen = 1 + maxLen(x-2, y);
  7.                     jumped[x-1][y] = false;
  8.             }
  9.             /* do the same thing for right, up, down */
  10.             return max(leftLen, rightLen, upLen, downLen);
  11.     }
复制代码
提供一个DFS的思路,x y 代表坐标,board是数值 0, 1, 2,jumped是和board等大的boolean数组,指示一个坐标是不是已经被跳过. 牛人云集,一亩三分地
欢迎指正  大家集思广益啊

补充内容 (2014-11-16 05:18):. visit 1point3acres for more.
噢忘了说  我这假设player是1,只能跳过2的点

评分

参与人数 1大米 +3 收起 理由
davidzeng1990 + 3 回答的很好!

查看全部评分

回复 支持 1 反对 0

使用道具 举报

我的人缘0
Adeath 发表于 2014-11-16 05:32:10 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
还有。。也可以把结果存储起来  这样比较节省内存  比如这样。。
  1.   int maxLen (int x, int y){
  2.             // len[][] is initialized as all -1. Waral 博客有更多文章,
  3.             if (len[x][y]>=0) return len[x][y];  // already know. more info on 1point3acres
  4.         int leftLen = 0;
  5.         if (x-2>=0 && board[x-2][y]==0 && board[x-1][y]==2 && !jumped[x-1][y]){
  6.                 // left is an opposite and left-1 is empty and not jumped, jump left
  7.                 jumped[x-1][y] = true;
  8.                 leftLen = 1 + maxLen(x-2, y);
  9.                 jumped[x-1][y] = false;
  10.         }
  11.         /* do the same thing for right, up, down */
  12.         len[x][y] = max(leftLen, rightLen, upLen, downLen);
    . Waral 博客有更多文章,
  13.         return len[x][y];
  14. }
复制代码
回复 支持 反对

使用道具 举报

头像被屏蔽
我的人缘0
jy02677290 发表于 2014-11-16 08:26:23 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| davidzeng1990 发表于 2014-11-16 08:46:12 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
就和咱们玩的跳棋一个规则,player 1 可以跳过 player 2的棋子,求某一棋子最远能跳多少步
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| davidzeng1990 发表于 2014-11-16 08:46:25 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
就和咱们玩的跳棋一个规则,player 1 可以跳过 player 2的棋子,求某一棋子最远能跳多少步
回复 支持 反对

使用道具 举报

我的人缘0
liuyuexj 发表于 2014-12-2 05:51:35 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Adeath 发表于 2014-11-16 05:16
提供一个DFS的思路,x y 代表坐标,board是数值 0, 1, 2,jumped是和board等大的boolean数组,指示一个坐标 ...

你好,我想请问下,这个DFS 的 stop conditions 要怎么写呢?就是什么时候开始return 呢?谢谢
回复 支持 反对

使用道具 举报

我的人缘0
Adeath 发表于 2014-12-2 06:00:50 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
liuyuexj 发表于 2014-12-2 05:51
你好,我想请问下,这个DFS 的 stop conditions 要怎么写呢?就是什么时候开始return 呢?谢谢

停止的条件就是四个方向都不能继续跳了 也就是四个if 都不成立  因为只有进入if的情况下才会调用递归  所以如果四个if都不成立  程序就不会调用任何递归 直接return 0
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
liuyuexj 发表于 2014-12-2 06:09:56 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Adeath 发表于 2014-12-2 06:00
停止的条件就是四个方向都不能继续跳了 也就是四个if 都不成立  因为只有进入if的情况下才会调用递归  所 ...
. 围观我们@1point 3 acres
哦,明白了,谢谢啦
回复 支持 反对

使用道具 举报

我的人缘0
xjwun 发表于 2015-2-12 10:24:38 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
额 如果旁边的不是对手的棋,是0, 会跳过去么?是跳过去就停止吗? 比如 0,1,0, 这种?
回复 支持 反对

使用道具 举报

我的人缘0
jianghaon0 发表于 2015-2-12 22:41:25 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这题目是让你求在i,j位置最远能跳几步。用dp做dp[i][j]表示i, j位置能跳最大步数
dp[i][j] = max(dp[i - 2][j], dp[i + 2][j], dp[i][j - 2], dp[i][j + 2]) + 1.
递归的时候你要记住这次跳过的对手的棋子(因为一个棋子只能跳过一次)。回退的时候在把对手棋子设成没有跳过。
具体思路就是这样。
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /3 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-6-19 08:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表