C++, List, Easy code. Note: move head to tail is valid operation!


  • 1
    L

    I have spent some time understand the logic that move the head->tail is valid. For example, a 3*3 grid, once you have 4 points (0,0), (0,1), (1,1), (1,0), where head is (0,0), and tail is (1, 0), if you move down (D), then the whole body get moved, and it is valid as (1,0), (0,0), (0, 1), (1, 1). This is the tricky part of this question.

    public: 
    list<pair<int, int>> snake;
    queue<pair<int, int>> foodque;
    pair<int, int> currfood;
    int m=0, n=0, totalFood = 0;
    bool hasDied = false, isNotOccupied = true;
    
    SnakeGame(int width, int height, vector<pair<int, int>> food) {
    	m = height; n = width;
    	for (pair<int, int>& fi : food) {  foodque.push(fi); }
    	currfood = foodque.front();
    	foodque.pop();
    	totalFood = food.size();
    	snake.push_back({ 0, 0 });
    	isNotOccupied = !isOccupied(currfood);
    }
    
    /** Moves the snake.
    @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
    @return The game's score after the move. Return -1 if game over.
    Game over when snake crosses the screen boundary or bites its body. */
    int move(string direction) {
        // time complexity is O(N), where N is the length of the snake
        
    	if (hasDied) { return -1; }
    	pair<int, int> front = snake.front();
    	pair<int, int> next = nextMove(front, direction);
    
    	if (!isValid(next)) {
    		hasDied = true;
    		return -1;
    	}
    
    	bool meetFood = false;
    	if (next.first == currfood.first
    		&& next.second == currfood.second
    		&& totalFood > 0
    		&& isNotOccupied) {
    		--totalFood;
    		meetFood = true;
    		if (foodque.size() > 0) {
    			currfood = foodque.front(); // get next one
    			foodque.pop();
    		}
    	}
    
    	snake.push_front(next);
    	if (!meetFood) {
    		snake.pop_back();
    	}
    
        // after each move, update the currfood information to 
        // see if it can be updated
    	if (!isNotOccupied && totalFood>0) {
    		isNotOccupied = !isOccupied(currfood);
    	}
    
    	return snake.size() - 1;
    }
    
    bool isOccupied(pair<int, int>& currfood) {
    	// by occupied, it means it is not adjacent to the head or tail
    
    	for (pair<int, int>& p : snake) {
    		if (currfood.first == p.first && currfood.second == p.second) {
    			return true;
    		}
    	}
    	return false;
    }
    
    bool isValid(pair<int, int>& move) {
    	if (move.first < 0 || move.first >= m
    		|| move.second < 0 || move.second >= n) {
    		return false;
    	}
        
        // NOTE that: if head==tail is okay
        pair<int, int> tail = snake.back();
        if(move.first==tail.first && move.second==tail.second) { return true; }
        // check if the snake will move the head to its other body (not tail)
    	for (pair<int, int>& p : snake) {
    		if (p.first == move.first && p.second == move.second) {
    			return false;
    		}
    	}
    	return true;
    }
    pair<int, int> nextMove(pair<int, int>& curr, string dir) {
    	if (dir == "U") { return{ curr.first - 1, curr.second }; }
    	if (dir == "L") { return{ curr.first, curr.second - 1 }; }
    	if (dir == "R") { return{ curr.first, curr.second + 1 }; }
    	return{ curr.first + 1, curr.second };
    }

  • 0

    It's naive but works OK. when given a direction, we can get the position of next move, and see if the move is out of boundary,or there's food there, or it's just a normal move.

    public class SnakeGame{
    int[][] food;
    int width;
    int height;
    int index;
    Deque<String> q;
    public static final HashMap<String,int[]> map=new HashMap<String,int[]>(){
    	{
    		put("U",new int[]{-1,0});
    		put("D",new int[]{1,0});
    		put("L",new int[]{0,-1});
    		put("R",new int[]{0,1});
    	}
    };
    public SnakeGame(int width,int height,int[][] food){
    	this.food=food;
        this.width=width;
    	this.height=height;
    	int index;
    	q=new LinkedList<>();
    	q.offer(new String("0 0"));
    }
    
    public int move(String direction){
    	String[] curr=q.peekLast().split(" ");
    	int[] dir=map.get(direction);
        //based on the direction given, we derive next move
        int x=Integer.parseInt(curr[0])+dir[0];
    	int y=Integer.parseInt(curr[1])+dir[1];
    
    	//if next move will go beyond the boundary, or cross snake's body
    	if(x<0||x>height-1||y<0||y>width-1||q.contains(x+" "+y)&&!q.peek().equals(x+" "+y)){
    		return -1;
    	}
           //if there's food on the next move, then this position will become part of the snake body
    	if(index<food.length){
    		int xFood=food[index][0];
    		int yFood=food[index][1];
    		if(x==xFood&&y==yFood){
    			q.offer(x+" "+y);
    			index++;
    			return index;
    		}
    	}
        
        //normal move:neither we go cross boundary,nor we get food on the next move;we just move the   snake one step forward
    	q.offer(x+" "+y);
    	q.poll();
    	return index;
    }
    

    }


  • 0

    Hey I like your answer and upvote it for sure! I wrote another one and try to post it..I've never posted and it seems that I am posting at wrong place, hope you don't mind:)


  • 0
    L

    thanks, it is also my first time to get an up vote ^_^


Log in to reply
 

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