instant

2D版frog jump，规定跳跃方向是右或下方。

基本的思路就是依次动态规划，没有什么不同。只是需要两个map来对每个石头进行行和列的索引。

下面的代码我也没有检查，嗯。

package snapchat;


import java.util.*;

public class FrogJump2D {
    class Point{
        int x;
        int y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public boolean canCross(List<int[]> stones){
        Map<Integer,Map<Integer,Point>> rowsDic = new TreeMap<>();
        Map<Integer,Map<Integer,Point>> colsDic = new TreeMap<>();
        Map<Point,Set<Integer>> mp = new HashMap<>();


        for(int[] stone : stones){
            int x = stone[0];
            int y = stone[1];

            Point p = new Point(x,y);
            if(!rowsDic.containsKey(x))rowsDic.put(x,new TreeMap<Integer, Point>());
            if(!colsDic.containsKey(y))colsDic.put(y,new TreeMap<Integer, Point>());
            rowsDic.get(x).put(y,p);
            colsDic.get(y).put(x,p);
            mp.put(p,new HashSet<Integer>());

        }

        if(stones.size() <= 1)return true;

        Point start = rowsDic.get(0).get(0);
        mp.get(start).add(0);
        int[] last = stones.get(stones.size() - 1);
        Point end = rowsDic.get(last[0]).get(last[1]);


        for(int row : rowsDic.keySet()){
            for(int col : rowsDic.get(row).keySet()){
                Point p = rowsDic.get(row).get(col);
                for(int step : mp.get(p)){
                    int[] d = new int[]{-1,0,1};
                    for(int i = 0; i < 3; i++){
                        int hor = step + col + d[i];
                        int ver = step + row - 1;

                        if(hor > col && rowsDic.get(row).containsKey(hor)){
                            Point hp = rowsDic.get(row).get(hor);
                            mp.get(hp).add(step + d[i]);
                        }
                        if(ver > row && colsDic.get(col).containsKey(ver)){
                            Point vp = colsDic.get(col).get(ver);
                            mp.get(vp).add(step + d[i]);
                        }
                    }

                }



            }
        }

        return mp.get(end).size() != 0;







    }
}