NTU IM DSAP Final Project

Judge Time:
- 06/29: 2100
- 06/30: 0000, 0300, 1200, 1800
- 06/31: 0000(DEADLINE)
Submission Way:
- Go to the page for DSAP(Data Structure and Advanced Programming)
- Enter the homework page and click the final project
- Archive Snake.h and Snake.cpp and submit the archived file.

Problem Description

There will only be 4 walls and 1 point in the simplest map i.e. first stage. New rules will be released when the student passing the first stage. The rule of current second stage is that there will be 4 walls and multi-points, and the grade of each point is different.
No matter what points the snake eats, the length of snake will only increase by 1 unit.
The map only changes when snake eats the point.

At first stage, there is no any constraint.
At second stage, the step limit is 8000 steps and execution time limit is 2 minutes. Also, there will be obstacles in the map.

Generate BFS step map (delete current tail while moving)
Find nearest ScorePoint. Track path and follow the direction (can modify to whole path)
If no valid ScorePoint exists, Move to (Random) direction.

Generate BFS step map from real Snake S1. Sort the ScorePoint with step length. Start with nearest ScorePoint, get the virtual snake S2 position (while S1 eat the food). If we can find path from S2's head to its tail. Track this path (P1) and follow the whole path from S1 to S2.
If there's no ScorePoint valid, Compute the longest path (P2) from S1's head to its tail. follow this path's first direction.
If no longest path exist, follow the direction that makes S1 the farthest from the food.