My code is right but Time Limit Exceeded


  • 0
    G
    class pair{
        int h;
        int w;
        pair(int h, int w){
            this.h = h;
            this.w = w;
        }
    }
    
    
    public class SnakeGame {
        int[][] matrix;
        int[][] food;
        int y = 0; //用来指向蛇头坐标
        int x = 0; //用来指向蛇头坐标
        
        
        int foodseq = 0;//该吃第几个(index)食物了
        int foodeat = 0;//现在吃了多少个
        
        Queue<pair> qq = new LinkedList<pair>();
        
        
        public SnakeGame(int width, int height, int[][] food) {
            matrix = new int[height][width];
            this.food = food;
            matrix[0][0]=99;
            qq.add(new pair(0,0));
        }
        
        public int move(String direction) {
            if(direction.equals("U")){
                pair tail = qq.peek();//看蛇尾是哪个点
                int th =tail.h;
                int tw = tail.w;
                matrix[th][tw]=0; //咬到蛇尾是可以的,因为蛇没吃东西动的时候,蛇尾也动了,东西不可能在蛇尾处
                
                if(y-1<0 || matrix[y-1][x]==99){//如果没有出界,或者没有咬到自己(可以咬到最末尾的地方)。
                    return -1;
                }
                matrix[th][tw]= 99; //再把蛇尾变回来,待会儿处理
                
                if(foodseq<food.length && food[foodseq][0]==y-1 && food[foodseq][1]==x){
                    foodseq++;
                    y--;
                    matrix[y][x]=99;
                    qq.add(new pair(y,x));
                    return (++foodeat);
                }
                else{//如果没吃到东西
                    pair temp = qq.poll();//这里一定要先处理蛇尾,如果先处理头,因为头的下一步有可能是刚刚尾巴的位置,待会儿处理尾就把头也变0
                    matrix[temp.h][temp.w]=0;
                    matrix[y-1][x]=99;
                    y--;
                    qq.add(new pair(y,x));
                    return foodeat;
                }
            }
            
            if(direction.equals("D")){
                pair tail = qq.peek();
                int th =tail.h;
                int tw = tail.w;
                matrix[th][tw]=0;
                
                if(y+1>=matrix.length || matrix[y+1][x]==99 ){
                    return -1;
                }
                
                matrix[th][tw]=99;
                
                if(foodseq<food.length && food[foodseq][0]==y+1 && food[foodseq][1]==x){
                    foodseq++;
                    y++;
                    matrix[y][x]=99;
                    qq.add(new pair(y,x));
                    return (++foodeat);
                }
                else{
                    pair temp = qq.poll();
                    matrix[temp.h][temp.w]=0;
                    matrix[y+1][x]=99;
                    y++;
                    qq.add(new pair(y,x));
                    
                    return foodeat;
                }
            }
            
             if(direction.equals("R")){
                 pair tail = qq.peek();
                 int th =tail.h;
                 int tw = tail.w;
                 matrix[th][tw]=0;
                 
                 if(x+1>=matrix[0].length || matrix[y][x+1]==99){
                     return -1;
                 }
                 matrix[th][tw]= 99;
                 if(foodseq<food.length && food[foodseq][0]==y && food[foodseq][1]==x+1){
                     foodseq++;
                     x++;
                     matrix[y][x]=99;
                     qq.add(new pair(y,x));
                     return (++foodeat);
                 }
                 else{
                     pair temp = qq.poll();
                     matrix[temp.h][temp.w]=0;
                     matrix[y][x+1]=99;
                     x++;
                     qq.add(new pair(y,x));
                     return foodeat;
                 }
             }
             if(direction.equals("L")){
                 pair tail = qq.peek();
                 int th =tail.h;
                 int tw = tail.w;
                 matrix[th][tw]=0;
                    
                 if(x==0 || matrix[y][x-1]==99){
                     return -1;
                 }
                 matrix[th][tw]=99;
                 if(foodseq<food.length && food[foodseq][0]==y && food[foodseq][1]==x-1){
                     foodseq++;
                     x--;
                     matrix[y][x]=99;
                     qq.add(new pair(y,x));
                     return (++foodeat);
                 }
                 else{
                     pair temp = qq.poll();
                     matrix[temp.h][temp.w]=0;
                     matrix[y][x-1]=99;
                     x--;
                     qq.add(new pair(y,x));
                     return foodeat;
                 }
             }
             return -1; 
        }
        
        
       
    }
    
    /**
     * Your SnakeGame object will be instantiated and called as such:
     * SnakeGame obj = new SnakeGame(width, height, food);
     * int param_1 = obj.move(direction);
     */

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.