[VI] Pacman

#preslozen algoritam a i pregolema tabla i ne mi funkcionira za slozeni test cases, sigurno e do mene zaradi slozenosta, no msilam deka logicka greska nemam
class Pacman(Problem):
    def __init__(self, initial, house=None):
        super().__init__(initial, house)

    def goal_test(self, state):
        return len(state[3])==0

    def successor(self, state):
        succ = {}
        pac_x=state[0]
        pac_y=state[1]
        nasoka=state[2]
        foods=state[3]
        new_foods=[]

        if nasoka=='istok' and self.check_valid((pac_x+1,pac_y)):
            if (pac_x+1,pac_y) in foods:
                for f in foods:
                    if f==(pac_x+1,pac_y):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["ProdolzhiPravo"]= (pac_x+1,pac_y,nasoka,tuple(new_foods))

        if nasoka=='zapad' and self.check_valid((pac_x-1,pac_y)):
            if (pac_x-1,pac_y) in foods:
                for f in foods:
                    if f==(pac_x-1,pac_y):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["ProdolzhiPravo"]= (pac_x-1,pac_y,nasoka,tuple(new_foods))


        if nasoka=='sever' and self.check_valid((pac_x,pac_y+1)):
            if (pac_x,pac_y+1) in foods:
                for f in foods:
                    if f==(pac_x,pac_y+1):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["ProdolzhiPravo"]= (pac_x,pac_y+1,nasoka,tuple(new_foods))

        if nasoka=='jug' and self.check_valid((pac_x,pac_y-1)):
            if (pac_x,pac_y-1) in foods:
                for f in foods:
                    if f==(pac_x,pac_y-1):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["ProdolzhiPravo"]= (pac_x,pac_y-1,nasoka,tuple(new_foods))



        if nasoka=='istok' and self.check_valid((pac_x-1,pac_y)):
            if (pac_x-1,pac_y) in foods:
                for f in foods:
                    if f==(pac_x-1,pac_y):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["ProdolzhiNazad"] = (pac_x-1, pac_y, 'zapad', tuple(new_foods))


        if nasoka=='zapad' and self.check_valid((pac_x+1,pac_y)):
            if (pac_x+1,pac_y) in foods:
                for f in foods:
                    if f==(pac_x+1,pac_y):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["ProdolzhiNazad"] = (pac_x+1, pac_y, 'istok', tuple(new_foods))

        if nasoka=='sever' and self.check_valid((pac_x,pac_y-1)):
            if (pac_x,pac_y-1) in foods:
                for f in foods:
                    if f==(pac_x,pac_y-1):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["ProdolzhiNazad"] = (pac_x, pac_y-1, 'jug', tuple(new_foods))

        if nasoka=='jug' and self.check_valid((pac_x,pac_y+1)):
            if (pac_x,pac_y+1) in foods:
                for f in foods:
                    if f==(pac_x,pac_y+1):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["ProdolzhiNazad"] = (pac_x, pac_y+1, 'sever', tuple(new_foods))

        if nasoka == 'istok' and self.check_valid((pac_x, pac_y + 1)):
            if (pac_x, pac_y + 1) in foods:
                for f in foods:
                    if f==(pac_x, pac_y + 1):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["SvrtiLevo"] = (pac_x, pac_y + 1, 'sever', tuple(new_foods))

        if nasoka == 'zapad' and self.check_valid((pac_x, pac_y - 1)):
            if (pac_x, pac_y - 1) in foods:
                for f in foods:
                    if f==(pac_x, pac_y - 1):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["SvrtiLevo"] = (pac_x, pac_y - 1, 'jug', tuple(new_foods))

        if nasoka == 'sever' and self.check_valid((pac_x - 1, pac_y)):
            if (pac_x - 1, pac_y) in foods:
                for f in foods:
                    if f==(pac_x - 1, pac_y):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["SvrtiLevo"] = (pac_x - 1, pac_y, 'zapad', tuple(new_foods))

        if nasoka == 'jug' and self.check_valid((pac_x + 1, pac_y)):
            if (pac_x + 1, pac_y) in foods:
                for f in foods:
                    if f==(pac_x + 1, pac_y):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["SvrtiLevo"] = (pac_x + 1, pac_y, 'istok', tuple(new_foods))

        if nasoka == 'istok' and self.check_valid((pac_x, pac_y - 1)):
            if (pac_x, pac_y - 1) in foods:
                for f in foods:
                    if f==(pac_x, pac_y - 1):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["SvrtiDesno"] = (pac_x, pac_y - 1, 'jug', tuple(new_foods))

        if nasoka == 'zapad' and self.check_valid((pac_x, pac_y + 1)):
            if (pac_x, pac_y + 1) in foods:
                for f in foods:
                    if f==(pac_x, pac_y + 1):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["SvrtiDesno"] = (pac_x, pac_y + 1, 'sever', tuple(new_foods))

        if nasoka == 'sever' and self.check_valid((pac_x + 1, pac_y)):
            if (pac_x + 1, pac_y) in foods:
                for f in foods:
                    if f==(pac_x + 1, pac_y):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["SvrtiDesno"] = (pac_x + 1, pac_y, 'istok', tuple(new_foods))

        if nasoka == 'jug' and self.check_valid((pac_x - 1, pac_y)):
            if (pac_x - 1, pac_y) in foods:
                for f in foods:
                    if f==(pac_x - 1, pac_y):
                        continue
                    else:
                        new_foods.append(f)
            else:
                for f in foods:
                    new_foods.append(f)
            succ["SvrtiDesno"] = (pac_x - 1, pac_y, 'zapad', tuple(new_foods))

        return succ



    @staticmethod
    def check_valid(state):
        if state[0]<0 or state[0]>4 or state[1]<0 or state[1]>4:
                return False
        #if state in ((0,9),(1,9),(2,9),(3,9),(6,9),(0,8),(8,8),(9,8),(4,7),(8,7),(9,7),(0,6),(3,6),(4,6),(5,6),(4,5),(1,4),(8,4),(9,4),(1,3),(1,2),(6,2),(4,1),(5,1),(6,1),(8,1),(6,0)):
        #    return False
        if state in ((1,1),(2,2),(3,4),(0,4)):
            return False
        return True
    def actions(self, state):
        return self.successor(state).keys()

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

if __name__ == "__main__":

    pac_x= int(input())
    pac_y= int(input())
    nasoka= input()
    n= int(input())
    foods= []
    for _ in range(n):
        x, y = map(int, input().split(','))
        foods.append((x, y))


    pacman= Pacman((pac_x,pac_y,nasoka,tuple(foods)))
    answer=breadth_first_graph_search(pacman)

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