刚面完的snapchat 估计挂了

hedayue 发表于 2016-4-12 01:04
可以返回走之前走过的~~ 我也是被这个条件给困住了

能否用queue做bfs的思路呢，每次更新queue的时候保证从n到n+1步不会重叠。

kemeng1314 发表于 2016-4-12 08:50
能否用queue做bfs的思路呢，每次更新queue的时候保证从n到n+1步不会重叠。

bfs用来数所有的possible way不好做吧

xzt8350 发表于 2016-4-12 05:55
我也收到据信啦～

再接再厉！

加油加油~

hedayue 发表于 2016-4-12 21:36
bfs用来数所有的possible way不好做吧

我code写了下，感觉还可以，不知是否满足题意

public static int moveWaysFromAToB(int boardLength, int k, int Ax, int Ay, int Bx. int By) {
   
      int edgeX = boardLength-1;
      int edgeY = boardLength-1;
      int count = 0;
      int ways = 0;
   
      int[][] dir = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
      int[][] visit = new int[boardLength][boardLength];
      // find possible points after K steps.
   
      Queue<Point> que = new LinkedList<>();
      que.offer(new Point(Ax,Ay,0));
      visit[Ax][Ay] = 1;
   
      while (que.size()>0) {
         Point p = que.peek();
         if (p.l == k) break;
        
         visit[p.x][p.y] = 0;
        
         que.poll();
           
         int newX = p.x+xShift;
         int newY = p.y+yShift;
           
         for (int[] d:dir) {
           if (newX<0 || newX>=edgeX) continue;
           if (newY<0 || newY>=edgeY) continue;
           if (visit[newX][newY] == 1) continue;
              
           que.offer(new Point(newX,newY,p.l+1));
           visit[newX][newY] = 1;
              
         }
           
      }
        
         
      while (que.size()>0) {
        Point p = que.poll();        
        if (p.x == B.x && p.y == B.y) ways++;
      }
   
  
      return ways;
  }

kemeng1314 发表于 2016-4-13 10:33
我code写了下，感觉还可以，不知是否满足题意

public static int moveWaysFromAToB(int boardLength, ...

思路就是queue的头结点poll出来时候，当成没有visit过，这样符合可以走之前走过的坐标。然后把它相邻的八个点再依次放入queue，每放入新的点需要先保证同一层没有别的事先走过。当第一次peek出来的点是K 距离时就把当前所有点都判断一遍，是B点的算一种走法。

kemeng1314 发表于 2016-4-13 10:37
思路就是queue的头结点poll出来时候，当成没有visit过，这样符合可以走之前走过的坐标。然后把它相邻的八 ...

哦不好意思，其实不用visit记录，任何点都不用记录是否走过。把visit都统一删去就行，这里只是担心queue会存越来越多的点,如果k比较大的情况下。1*8*8*...

想问楼主两个问题：
第一题的DP解法是不是L(i,j,k)这种，然后按照步长计算L(i,j,k) = sum(eight_neigbors(m, n, k - 1))?
最后一道题GetToken是怎么实现的，是需要自己解析一个XML string吗？
谢谢

Jinyu_cs 发表于 2016-4-12 21:52
加油加油~

谢谢啦~   消息居然被隐掉了 刚才看见~~  

TsengJuiWang 发表于 2016-4-26 11:05
想问楼主两个问题：
第一题的DP解法是不是L(i,j,k)这种，然后按照步长计算L(i,j,k) = sum(eight_neigbors( ...

第一题的DP就说了下思路，没有具体写。我觉得你说的应该是对的~  
最后一个题 gettoken就是get到下一个xml元素。
我记不太清楚了哈  但是input是一个String， 里面有很多xml element，每次调用 就返回期中一个element。