一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2103|回复: 10
收起左侧

[找工就业] Epic OA 的jumper game

[复制链接] |试试Instant~ |关注本帖
davidzeng1990 发表于 2014-11-16 04:24:22 | 显示全部楼层 |阅读模式

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

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

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

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.
. 鍥磋鎴戜滑@1point 3 acres

各位大神,求这道题的解法,C++最好,java也可以。。。明天OA了,只能伸手了。。。求各位大神帮下忙。。。。。
Adeath 发表于 2014-11-16 05:16:43 | 显示全部楼层
  1. int maxLen (int x, int y){
  2.             int leftLen = 0;
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  3.             if (x-2>=0 && board[x-2][y]==0 && board[x-1][y]==2 && !jumped[x-1][y]){
    . visit 1point3acres.com for more.
  4.                     // left is an opposite and left-1 is empty and not jumped, jump left
  5.                     jumped[x-1][y] = true;
  6.                     leftLen = 1 + maxLen(x-2, y);
  7.                     jumped[x-1][y] = false;
  8.             }
  9.             /* do the same thing for right, up, down */. 鍥磋鎴戜滑@1point 3 acres
  10.             return max(leftLen, rightLen, upLen, downLen);
  11.     }
复制代码
提供一个DFS的思路,x y 代表坐标,board是数值 0, 1, 2,jumped是和board等大的boolean数组,指示一个坐标是不是已经被跳过
欢迎指正  大家集思广益啊

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

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

Adeath 发表于 2014-11-16 05:32:10 | 显示全部楼层
还有。。也可以把结果存储起来  这样比较节省内存  比如这样。。
  1.   int maxLen (int x, int y){
  2.             // len[][] is initialized as all -1-google 1point3acres
  3.             if (len[x][y]>=0) return len[x][y];  // already know-google 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);. Waral 鍗氬鏈夋洿澶氭枃绔,
  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);
  13.         return len[x][y];
  14. }
复制代码
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| davidzeng1990 发表于 2014-11-16 08:46:12 | 显示全部楼层
就和咱们玩的跳棋一个规则,player 1 可以跳过 player 2的棋子,求某一棋子最远能跳多少步
回复 支持 反对

使用道具 举报

 楼主| davidzeng1990 发表于 2014-11-16 08:46:25 | 显示全部楼层
就和咱们玩的跳棋一个规则,player 1 可以跳过 player 2的棋子,求某一棋子最远能跳多少步
回复 支持 反对

使用道具 举报

liuyuexj 发表于 2014-12-2 05:51:35 | 显示全部楼层
Adeath 发表于 2014-11-16 05:16
提供一个DFS的思路,x y 代表坐标,board是数值 0, 1, 2,jumped是和board等大的boolean数组,指示一个坐标 ...

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

使用道具 举报

Adeath 发表于 2014-12-2 06:00:50 | 显示全部楼层
liuyuexj 发表于 2014-12-2 05:51
你好,我想请问下,这个DFS 的 stop conditions 要怎么写呢?就是什么时候开始return 呢?谢谢

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

使用道具 举报

liuyuexj 发表于 2014-12-2 06:09:56 | 显示全部楼层
Adeath 发表于 2014-12-2 06:00
停止的条件就是四个方向都不能继续跳了 也就是四个if 都不成立  因为只有进入if的情况下才会调用递归  所 ...

哦,明白了,谢谢啦
回复 支持 反对

使用道具 举报

xjwun 发表于 2015-2-12 10:24:38 | 显示全部楼层
额 如果旁边的不是对手的棋,是0, 会跳过去么?是跳过去就停止吗? 比如 0,1,0, 这种?
回复 支持 反对

使用道具 举报

jianghaon0 发表于 2015-2-12 22:41:25 | 显示全部楼层
这题目是让你求在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.
递归的时候你要记住这次跳过的对手的棋子(因为一个棋子只能跳过一次)。回退的时候在把对手棋子设成没有跳过。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
具体思路就是这样。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 18:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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