[VI] Ghost on Skates

class GhostOnSkates(Problem):
    def __init__(self, initial, walls, n, goal=None):
        super().__init__(initial, goal)
        self.walls = walls
        self.n = n

    def actions(self, state):
        return self.successor(state).keys()

    def result(self, state, action):
        return self.successor(state)[action]

    def goal_test(self, state):
        return state == self.goal

    @staticmethod
    def check_valid(state, walls, n):
        if state in tuple(walls) or state[0]>n-1 or state[1]>n-1:
            return False
        return True

    def successor(self, state):
        successors = dict()

        ghost_pos= state
        holes= self.walls
        n= self.n

        new_x= ghost_pos[0]
        new_y= ghost_pos[1]+1
        new_ghost_pos= []
        new_ghost_pos.append(new_x)
        new_ghost_pos.append(new_y)

        if self.check_valid(tuple(new_ghost_pos),holes,n):
            successors["Gore 1"] = (tuple(new_ghost_pos))

        new_x= ghost_pos[0]
        new_y= ghost_pos[1]+2
        new_ghost_pos= []
        new_ghost_pos.append(new_x)
        new_ghost_pos.append(new_y)

        if self.check_valid(tuple(new_ghost_pos),holes,n):
            successors["Gore 2"] = (tuple(new_ghost_pos))

        new_x= ghost_pos[0]
        new_y= ghost_pos[1]+3
        new_ghost_pos= []
        new_ghost_pos.append(new_x)
        new_ghost_pos.append(new_y)

        if self.check_valid(tuple(new_ghost_pos),holes,n):
            successors["Gore 3"] = (tuple(new_ghost_pos))

        new_x= ghost_pos[0]+1
        new_y= ghost_pos[1]
        new_ghost_pos= []
        new_ghost_pos.append(new_x)
        new_ghost_pos.append(new_y)

        if self.check_valid(tuple(new_ghost_pos),holes,n):
            successors["Desno 1"] = (tuple(new_ghost_pos))


        new_x= ghost_pos[0]+2
        new_y= ghost_pos[1]
        new_ghost_pos= []
        new_ghost_pos.append(new_x)
        new_ghost_pos.append(new_y)

        if self.check_valid(tuple(new_ghost_pos),holes,n):
            successors["Desno 2"] = (tuple(new_ghost_pos))

        new_x= ghost_pos[0]+3
        new_y= ghost_pos[1]
        new_ghost_pos= []
        new_ghost_pos.append(new_x)
        new_ghost_pos.append(new_y)

        if self.check_valid(tuple(new_ghost_pos),holes,n):
            successors["Desno 3"] = (tuple(new_ghost_pos))

        return successors

    def h(self, node):
        state= node.state
        ghost_pos= state
        goal_pos= self.goal
        #print(node.state)
        return (abs(ghost_pos[0]-goal_pos[0]) + abs(ghost_pos[1]-goal_pos[1]))/3


if __name__ == '__main__':
    n = int(input())
    ghost_pos = (0, 0)
    goal_pos = (n - 1, n - 1)

    num_holes = int(input())
    holes = list()
    for _ in range(num_holes):
        holes.append(tuple(map(int, input().split(','))))

    problem = GhostOnSkates(ghost_pos, holes, n, goal_pos)

    answer= astar_search(problem)

    if answer is None:
        print("None")
    else:
        print(answer.solution())