Epic OA 的jumper game

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,

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

color:rgb(242, 242, 242)">各位大神，求这道题的解法，C++最好，java也可以。。。明天OA了，只能伸手了。。。求各位大神帮下忙。。。。。

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]){
   
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 */
   
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.   int maxLen (int x, int y){
   
2.             // len[][] is initialized as all -1
   
3.             if (len[x][y]>=0) return len[x][y];  // already know
   
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);
    
13.         return len[x][y];
    
14. }

复制代码

就和咱们玩的跳棋一个规则，player 1 可以跳过 player 2的棋子，求某一棋子最远能跳多少步

就和咱们玩的跳棋一个规则，player 1 可以跳过 player 2的棋子，求某一棋子最远能跳多少步

Adeath 发表于 2014-11-16 05:16
提供一个DFS的思路，x y 代表坐标，board是数值 0, 1, 2，jumped是和board等大的boolean数组，指示一个坐标 ...

你好，我想请问下，这个DFS 的 stop conditions 要怎么写呢？就是什么时候开始return 呢？谢谢

liuyuexj 发表于 2014-12-2 05:51
你好，我想请问下，这个DFS 的 stop conditions 要怎么写呢？就是什么时候开始return 呢？谢谢

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

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

哦，明白了，谢谢啦

额 如果旁边的不是对手的棋，是0， 会跳过去么？是跳过去就停止吗？ 比如 0,1,0, 这种？