class CornersProblem(search.SearchProblem):
    """
   This search problem finds paths through all four corners of a layout.

   You must select a suitable state space and successor function
   """

    def __init__(self, startingGameState):
        self.visitedCorners=(0,0,0,0)
        self.walls = startingGameState.getWalls()
        self.startingPosition = startingGameState.getPacmanPosition()
        top, right = self.walls.height-2, self.walls.width-2
        self.corners = ((1,1), (1,top), (right, 1), (right, top))
        for corner in self.corners:
            if not startingGameState.hasFood(*corner):
                print 'Warning: no food in corner ' + str(corner)
        self._expanded = 0 # DO NOT CHANGE; Number of search nodes expanded

    def getStartState(self):

        return (self.startingPosition,self.visitedCorners);


    def isGoalState(self, state):

        position,visitedCorners=state
        if visitedCorners==(1,1,1,1):
            return 1

    def getSuccessors(self, state):

        successors = []
        position,visitedCorners=state
        x,y=position
        for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]:
            dx,dy=Actions.directionToVector(action)
            nextx, nexty = int(x + dx), int(y + dy)
            hitsWall = self.walls[nextx][nexty]
            if not hitsWall :
                NextNode=(nextx, nexty)
                if NextNode in self.corners:
                    a = list(visitedCorners)
                    a[self.corners.index(NextNode)]=1
                    visitedCorners = tuple(a)
                Nextcost=1
                successor=((NextNode,visitedCorners),action,Nextcost)
                successors.append(successor)
        return successors


    def getCostOfActions(self, actions):
        """
       Returns the cost of a particular sequence of actions.  If those actions
       include an illegal move, return 999999.  This is implemented for you.
       """
        if actions == None: return 999999
        x,y= self.startingPosition
        for action in actions:
            dx, dy = Actions.directionToVector(action)
            x, y = int(x + dx), int(y + dy)
            if self.walls[x][y]: return 999999
        return len(actions)