def registerInitialState(self, state):
        "This method is called before any moves are made."
        "*** YOUR CODE HERE ***"
        walls = state.getWalls()
        top, right = walls.height-2, walls.width-2
        self.top, self.right = top, right
        self.corners = ((1,1), (1,top), (right, 1), (right, top))
        corners_path = [((mazeDistance(state.getPacmanPosition(), c, state), c)) for c in self.corners]
        prob = PositionSearchProblem(state, start=state.getPacmanPosition(), goal=min(corners_path)[1], warn=False)
        self.moves = search.bfs(prob)
        foodGrid = state.getFood()
        # walls = state.getWalls()
        # start = state.getPacmanPosition()
        mcdonalds = []
        for x, row in enumerate(foodGrid):
            for y, cell in enumerate(row):
                if foodGrid[x][y]:
                    distance = mazeDistance(state.getPacmanPosition(), (x,y), state)
                    #distance = find_manhattan_distance(state.getPacmanPosition(), (x,y))

        if mcdonalds:
            coordinate = min(mcdonalds)[1]
            prob = PositionSearchProblem(state, start=start, goal=coordinate, warn=False)
            self.moves = search.bfs(prob)
            return
        self.moves = []

def foodHeuristic(state, problem):
    """
    Your heuristic for the FoodSearchProblem goes here.

    This heuristic must be consistent to ensure correctness.  First, try to come up
    with an admissible heuristic; almost all admissible heuristics will be consistent
    as well.

    If using A* ever finds a solution that is worse uniform cost search finds,
    your heuristic is *not* consistent, and probably not admissible!  On the other hand,
    inadmissible or inconsistent heuristics may find optimal solutions, so be careful.

    The state is a tuple ( pacmanPosition, foodGrid ) where foodGrid is a
    Grid (see game.py) of either True or False. You can call foodGrid.asList()
    to get a list of food coordinates instead.

    If you want access to info like walls, capsules, etc., you can query the problem.
    For example, problem.walls gives you a Grid of where the walls are.

    If you want to *store* information to be reused in other calls to the heuristic,
    there is a dictionary called problem.heuristicInfo that you can use. For example,
    if you only want to count the walls once and store that value, try:
      problem.heuristicInfo['wallCount'] = problem.walls.count()
    Subsequent calls to this heuristic can access problem.heuristicInfo['wallCount']
    """
    position, foodGrid = state
    "*** YOUR CODE HERE ***"
    distances_x =[]
    distances_manhattan = []
    distances_y = []
    maxes =[]

    global farthest_Coordinate

    for coordinate in foodGrid.asList():
        distances_x.append((abs(position[0] - coordinate[0])))
        distances_y.append(abs(position[1] - coordinate[1]))
        distances_manhattan.append((abs(position[0] - coordinate[0])) + (abs(position[1] - coordinate[1])))

    for coordinate in foodGrid.asList():
        if max(distances_manhattan) == (abs(position[0] - coordinate[0])) + (abs(position[1] - coordinate[1])):
            farthest_Coordinate = coordinate
    if len(foodGrid.asList()) < 3:
        prob = PositionSearchProblem(problem.startingGameState, start=position, goal=farthest_Coordinate, warn=False)
        if ((search.bfs(prob))) != None:
            maxes.append(len(search.bfs(prob)))
    elif len(foodGrid.asList()) > 9:
        prob = PositionSearchProblem(problem.startingGameState, start=position, goal=farthest_Coordinate, warn=False)
        if ((search.bfs(prob))) != None:
            maxes.append(len(search.bfs(prob)))

    if len(distances_x) == 0:
        return 0
    maxes.append(max(distances_manhattan))
    maxes.append((max(distances_x)+max(distances_y)))
    maxes.append(len(foodGrid.asList()))
    return max(maxes)

 def getAction(self, state):
     """
     From game.py:
     The Agent will receive a GameState and must return an action from
     Directions.{North, South, East, West, Stop}
     """
     "*** YOUR CODE HERE ***"
     if self.foodPos == state.getPacmanPosition():
         offset = 5
         foodcount = []
         while len(foodcount) == 0:
             for food in state.getFood().asList():
                 if util.manhattanDistance(state.getPacmanPosition(), food) < offset:
                     foodcount.append(food)
             offset += 2
         maze = []
         for food in foodcount:
             point1, point2 = state.getPacmanPosition(), food
             x1, y1 = point1
             x2, y2 = point2
             walls = state.getWalls()
             assert not walls[x1][y1], 'point1 is a wall: ' + point1
             assert not walls[x2][y2], 'point2 is a wall: ' + str(point2)
             prob = PositionSearchProblem(state, start=point1, goal=point2, warn=False, visualize=False)
             self.nextPos = util.Queue()
             searchp = search.bfs(prob)
             maze.append((len(searchp), searchp, food))
         mini = min(maze)
         self.foodPos = mini[2]
         for direction in mini[1]:
             self.nextPos.push(direction)
     return self.nextPos.pop()

    def findPathToClosestDot(self, gameState):

        """

        Returns a path (a list of actions) to the closest dot, starting from

        gameState.

        """

        # Here are some useful elements of the startState

        startPosition = gameState.getPacmanPosition()

        food = gameState.getFood()

        walls = gameState.getWalls()

        problem = AnyFoodSearchProblem(gameState)

        actions = search.bfs(problem)

        

        return actions 

        "*** YOUR CODE HERE ***"

        util.raiseNotDefined()

    def once(self, state):
        if not util.packet_queue.empty():
            return

        player = state.me()

        self.tryPutBomb(state, player)

        safe_map = state.game_map.safeMap()

        playerPos = util.coordToPos(player.x, player.y)
        gridX, gridY = util.posToGrid(playerPos)
        if safe_map[gridX][gridY]:
            return

        def __internal_safe(pos):
            gridX, gridY = util.posToGrid(pos)
            return safe_map[gridX][gridY]
        actions = search.bfs(state.game_map, playerPos, __internal_safe)

        move = actions[0]
        if state.moveValidForMe(actions[0]):
            self.goMove(player, move)
        else:
            # If unable to go to specified pos now, go to current center first
            centerX, centerY = util.posToCoord(playerPos)
            dx, dy = (centerX - player.x, centerY - player.y)
            self.goMove(player, Direction.byDistance(dx, dy))

    def findPathToClosestDot(self, gameState):
        """
        Returns a path (a list of actions) to the closest dot, starting from
        gameState.
        """
        # Here are some useful elements of the startState
        position = gameState.getPacmanPosition()
        food = gameState.getFood()
        walls = gameState.getWalls()
        problem = AnyFoodSearchProblem(gameState)
        foodList = food.asList()


        "*** YOUR CODE HERE ***"
        
        closestDist = 999999
        closestFood = None
        for food in foodList:
          dist = ((position[0] - food[0])**2 + (position[1] - food[1])**2)**0.5
          if dist < closestDist :
            closestDist = dist
            closestFood = food
        
        problem.goal = closestFood
        return search.bfs(problem)

 def getAction(self, state):
     """
     From game.py:
     The Agent will receive a GameState and must return an action from
     Directions.{North, South, East, West, Stop}
     """
     "*** YOUR CODE HERE ***"
     if not self.moves:
         currx, curry = state.getPacmanPosition()
         walls = state.getWalls()
         mcdonalds = []
         foodGrid = state.getFood()
         for i in range(currx-2, currx+1):
             for j in range(curry-2, curry+1):
                 if i >=0 and j>= 0 and i <= self.right and j <= self.top and foodGrid[i][j] and not walls[i][j]:
                     score = find_manhattan_distance(state.getPacmanPosition(), (i, j)), 0, (i, j)
                     mcdonalds.append(score)
         if not mcdonalds:
             for x, row in enumerate(foodGrid):
                 for y, cell in enumerate(row):
                     if foodGrid[x][y]:
                         score = mazeDistance(state.getPacmanPosition(), (x,y), state), self.adjacentDots(state, x,y), (x, y)
                         mcdonalds.append(score)
         if mcdonalds:
             coordinate = min(mcdonalds)[2]
             prob = PositionSearchProblem(state, start=state.getPacmanPosition(), goal=coordinate, warn=False)
             self.moves.extend(search.bfs(prob))
     a = self.moves.pop(0)
     return a

 def mazeDistance(self,point1,point2):
     for food in self.getFood():
         if food not in self.myWalls:
             prob = PositionSearchProblem(self, start=point1, goal=point2, warn=False)
             dist = len(search.bfs(prob))
             self.Queue.push(food,dist)
             self.min = self.min if self.min<dist else dist

 def findPathToClosestDot(self, gameState):
     """
     Returns a path (a list of actions) to the closest dot, starting from
     gameState.
     """
     # Here are some useful elements of the startState
     return search.bfs(AnyFoodSearchProblem(gameState))

def mazeDistance(point1, point2, gameState):

    """

    Returns the maze distance between any two points, using the search functions

    you have already built. The gameState can be any game state -- Pacman's

    position in that state is ignored.



    Example usage: mazeDistance( (2,4), (5,6), gameState)



    This might be a useful helper function for your ApproximateSearchAgent.

    """

    x1, y1 = point1

    x2, y2 = point2

    walls = gameState.getWalls()

    assert not walls[x1][y1], 'point1 is a wall: ' + point1

    assert not walls[x2][y2], 'point2 is a wall: ' + str(point2)

    prob = PositionSearchProblem(gameState, start=point1, goal=point2, warn=False, visualize=False)

    return len(search.bfs(prob))

    def findPathToClosestDot(self, gameState):
        "Returns a path (a list of actions) to the closest dot, starting from gameState"
        # Here are some useful elements of the startState
        pacman_position = gameState.getPacmanPosition()
        food_grid = gameState.getFood()
        walls = gameState.getWalls()
        problem = AnyFoodSearchProblem(gameState)

        food_list = food_grid.asList()

        closest_food_distance = sys.maxint
        closest_food = None

        for food in food_list:
            food_distance = abs(pacman_position[0] - food[0]) + abs(pacman_position[1] - food[1])
            if food_distance < closest_food_distance:
                closest_food_distance = food_distance
                closest_food = food

        point1 = pacman_position
        point2 = closest_food

        x1, y1 = point1
        x2, y2 = point2
        walls = gameState.getWalls()
        assert not walls[x1][y1], 'point1 is a wall: ' + point1
        assert not walls[x2][y2], 'point2 is a wall: ' + str(point2)
        prob = PositionSearchProblem(gameState, start=point1, goal=point2, warn=False, visualize=False)

        return search.bfs(prob)

 def maze(point1, point2):
     x1, y1 = point1
     x2, y2 = point2
     assert not walls[x1][y1], 'point1 is a wall: ' + point1
     assert not walls[x2][y2], 'point2 is a wall: ' + str(point2)
     prob = PositionSearchProblem(problem.startingGameState, start=point1, goal=point2, warn=False)
     return len(search.bfs(prob))

def cornersHeuristic(state, problem):
    """
    A heuristic for the CornersProblem that you defined.

      state:   The current search state
               (a data structure you chose in your search problem)

      problem: The CornersProblem instance for this layout.

    This function should always return a number that is a lower bound
    on the shortest path from the state to a goal of the problem; i.e.
    it should be admissible (as well as consistent).
    """
    #corners = problem.corners # These are the corner coordinates
    #walls = problem.walls # These are the walls of the maze, as a Grid (game.py)
    
    xy1 = state[0]
    distance = [] 
    for s in state[1]:
        xy2 = s
        xyxy = xy1[0],xy1[1],xy2[0],xy2[1]
        if xyxy in problem.heuristicInfo.keys():
            distance.append(problem.heuristicInfo[xyxy])
        else:
            prob = PositionSearchProblem(problem.state, start=xy1, goal=xy2, warn=False, visualize=False)
	        d = len(search.bfs(prob))
	        problem.heuristicInfo.update({xyxy:d})
	        distance.append(d)
        distance.sort()

    def getAction(self, state):
        """
        From game.py:
        The Agent will receive a GameState and must return an action from
        Directions.{North, South, East, West, Stop}
        """
       
        
        if len(self.answer) > 0:
            answer = self.answer[0]
            self.answer = self.answer[1:]
            return answer
        else:
            self.time = 1

        if state.getFood().count() <= 20 and self.time == 1:
            problem = FoodSearchProblem(state)
            self.answer = search.aStarSearch(problem, foodHeuristic)
            answer = self.answer[0]
            self.answer = self.answer[1:]
            return answer

        
        problem = AnyFoodSearchProblem(state)
        self.answer = search.bfs(problem)
        answer = self.answer[0]
        self.answer = self.answer[1:]
        return answer

def cornersHeuristic(state, problem):
    """
    A heuristic for the CornersProblem that you defined.

      state:   The current search state
               (a data structure you chose in your search problem)

      problem: The CornersProblem instance for this layout.

    This function should always return a number that is a lower bound
    on the shortest path from the state to a goal of the problem; i.e.
    it should be admissible (as well as consistent).
    """
    corners = problem.corners # These are the corner coordinates
    walls = problem.walls # These are the walls of the maze, as a Grid (game.py)

    "*** YOUR CODE HERE ***"
    #Manhatten/Euclid to closest unreached corner
    Manhattens = []
    for i, corner in enumerate(corners):
        if not state[1][i]:
            #Manhattens.append(abs(state[0][0] - corner[0]) + abs(state[0][1] - corner[1]))
            #Manhattens.append(((state[0][0] - corner[0]) ** 2 + (state[0][1] - corner[1]) **2 )** 0.5)
            x1, y1 = state[0]
            x2, y2 = corner
            #assert not walls[x1][y1], 'point1 is a wall: ' + state[0]
            #assert not walls[x2][y2], 'point2 is a wall: ' + str(corner)
            prob = PositionSearchProblem(problem.startgameState, start=state[0], goal=corner, warn=False, visualize=False)
            Manhattens.append(len(search.bfs(prob)))
    if len(Manhattens) == 0:
        Manhattens.append(0)
    return Manhattens[0]

 def findPathToClosestDot(self, gameState):
     "Returns a path (a list of actions) to the closest dot, starting from gameState"
     # Here are some useful elements of the startState
     startPosition = gameState.getPacmanPosition()
     food = gameState.getFood()
     walls = gameState.getWalls()
     problem = AnyFoodSearchProblem(gameState)
     return search.bfs(problem)

def main():
    search_type = sys.argv[1]
    board = sys.argv[2]
    if search_type == 'bfs':
        return bfs(EightPuzzle(board))
    elif search_type == 'dfs':
        return dfs(EightPuzzle(board))
    return ast(EightPuzzle(board, heuristic=manhattan_distance))

def betterEvaluationFunction(currentGameState):
    """
    Your extreme ghost-hunting, pellet-nabbing, food-gobbling, unstoppable
    evaluation function (question 5).

    DESCRIPTION: 
    there are several issues that I take into account
    1.the shortest path to a food. I may use the greedy algorithm to search for
      all the dots, so that the shorter pacman's distance, the higher score will
      be. -negative -reciprocal -important
    2.numbers of food left. I won't explain too much as it's obvious.
      -negative -normal -in standard score
    3.the utility caring the distance with ghost. I consider the ghost 2 grid away
      from me is safe as I won't care too much about a ghost that can't eat pacman
      within one or two steps, but when the ghost is two or one grid away, I may be
      cautious for they may eat me within there ability.
      -negative -important
    4.if I've win or lose, it has the most weight
      -depends -most important -in standard score
    5.when the ghost is safe, I may not take it into account that I will keep it away
      -depends -not so important -in standard score
    6.states of ghost. If pacman can make the ghost into white, it may be very pleased.
      -positive -not so important
  """
    if currentGameState.isWin() or currentGameState.isLose():
        return currentGameState.getScore()
    shortestPathProblem = searchAgents.AnyFoodSearchProblem(currentGameState)
    shortestPathLen=len(search.bfs(shortestPathProblem)) #first parameter
    foodLeft=currentGameState.getNumFood() #second parameter
    ghostStates = currentGameState.getGhostStates()
    scaredTimes = [ghostState.scaredTimer for ghostState in ghostStates]
    position=currentGameState.getPacmanPosition()
    ghostThreat=0 #the third parameter
    for ghost in ghostStates:
        if scaredTimes[ghostStates.index(ghost)]<1:
            if util.manhattanDistance(ghost.configuration.pos,position)<=1:
                if util.manhattanDistance(ghost.configuration.pos,position)==0:
                    ghostThreat+=-10000
                else:
                    ghostThreat+=-300
            else:
                ghostThreat+=10.0/util.manhattanDistance(ghost.configuration.pos,position)
        else:
            ghostThreat+=0
    
    newFood=currentGameState.getFood()
    foodAttraction=0
    for i in range(newFood.width):
        for j in range(newFood.height):
            if newFood[i][j]:
                foodAttraction+=1.0/math.pow(util.manhattanDistance((i,j), position),2)
                
    totalScore=currentGameState.getScore() + 10*1.0/shortestPathLen + ghostThreat + foodAttraction
    return totalScore
    util.raiseNotDefined()

def on_click():
    '''
    This function defines the action of the 'Next' button.
    '''
    global algo, counter, next_button, romania_problem, start, goal
    romania_problem = GraphProblem(start.get(), goal.get(), romania_map)
    if "Breadth-First Tree Search" == algo.get():
        node = breadth_first_tree_search(romania_problem)
        if node is not None:
            final_path = bfts(romania_problem).solution()
            final_path.append(start.get())
            display_final(final_path)
            next_button.config(state="disabled")
        counter += 1
    elif "Depth-First Tree Search" == algo.get():
        node = depth_first_tree_search(romania_problem)
        if node is not None:
            final_path = dfts(romania_problem).solution()
            final_path.append(start.get())
            display_final(final_path)
            next_button.config(state="disabled")
        counter += 1
    elif "Breadth-First Search" == algo.get():
        node = breadth_first_search(romania_problem)
        if node is not None:
            final_path = bfs(romania_problem).solution()
            final_path.append(start.get())
            display_final(final_path)
            next_button.config(state="disabled")
        counter += 1
    elif "Depth-First Graph Search" == algo.get():
        node = depth_first_graph_search(romania_problem)
        if node is not None:
            final_path = dfgs(romania_problem).solution()
            final_path.append(start.get())
            display_final(final_path)
            next_button.config(state="disabled")
        counter += 1
    elif "Uniform Cost Search" == algo.get():
        node = uniform_cost_search(romania_problem)
        if node is not None:
            final_path = ucs(romania_problem).solution()
            final_path.append(start.get())
            display_final(final_path)
            next_button.config(state="disabled")
        counter += 1
    elif "A* - Search" == algo.get():
        node = astar_search(romania_problem)
        if node is not None:
            final_path = asts(romania_problem).solution()
            final_path.append(start.get())
            display_final(final_path)
            next_button.config(state="disabled")
        counter += 1

    def findPathToClosestDot(self, gameState):
        """
        Returns a path (a list of actions) to the closest dot, starting from
        gameState.
        """
        # Here are some useful elements of the startState
        startPosition = gameState.getPacmanPosition()
        food = gameState.getFood()
        walls = gameState.getWalls()
        problem = AnyFoodSearchProblem(gameState)

        "*** YOUR CODE HERE ***"
        return search.bfs(problem) # each food is a goal, just find a optimal one