import queue

class ConnerPoint():
    def __init__(self, no, x, y):
        self.__no = no
        self.__x = x
        self.__y = y

    def __repr__(self):
        return "<Point: [no={}, y={}, x={}]>".format(self.no, self.y, self.x)
    
    @property
    def no(self):
        return self.__no

    @property
    def x(self):
        return self.__x

    @property
    def y(self):
        return self.__y

class StateInfo():
    def __init__(self, no, west, north, east, south):
        self.no = no
        self.connected_no = [west, north, east, south]

class State():
    def __init__(self, row=-1, column=-1):
        self.row = row
        self.column = column

    def __repr__(self):
        return "<State: [{}, {}]>".format(self.row, self.column)

    def clone(self):
        return State(self.row, self.column)

    def __hash__(self):
        return hash((self.row, self.column))

    def __eq__(self, other):
        return self.row == other.row and self.column == other.column

class MazeBase():
    START = -1
    PATH = 0
    WALL = 1
    GOAL = 99
    _DEFAULT_REWARD = 0
    _UNCHANGED_REWARD = -1
    _GOAL_REWARD = 10

    def _search_longest_distance_Point(self, start_point, conner_points, state_inf_dic):
        check_visited_no = [False] * (len(conner_points) + 1)
        check_visited_no[start_point.no] = True

        q = queue.Queue()
        q.put(start_point)
        hop_count = 0

        l = [(start_point, hop_count)]
        while not q.empty():
            cp = q.get()
            state_info = state_inf_dic[State(cp.y, cp.x)]
            for connected_no in state_info.connected_no:
                if connected_no is not None and not check_visited_no[connected_no]:
                    hop_count += 1
                    ccp = list(filter(lambda p: p.no == connected_no, conner_points))[0]
                    l.append((ccp, hop_count))
                    q.put(ccp)
                    check_visited_no[connected_no] = True

        return max(l, key=(lambda x: x[1]))

    def create_maze(self, width, height):
        pass

    def load_maze(self, maze_map):
        self.maze_map = maze_map
        self.width = len(maze_map[0])
        self.height = len(maze_map)
        self.search_conner_points()
        self.create_conner_network()
        self._set_start_goal()

    def search_conner_points(self):
        if len(self.maze_map) == 0:
            print('not created maze')
            exit()

        conner_points = []
        conner_no = 1
        for i in range(1, self.height):
            for j in range(1, self.width):
                if self.maze_map[i][j] == MazeBase.PATH or self.maze_map[i][j] == MazeBase.START or self.maze_map[i][j] == MazeBase.GOAL :
                    wall_cnt = 0
                    if self.maze_map[i-1][j] == MazeBase.WALL:
                        wall_cnt += 1
                    if self.maze_map[i+1][j] == MazeBase.WALL:
                        wall_cnt += 1
                    if self.maze_map[i][j-1] == MazeBase.WALL:
                        wall_cnt += 1
                    if self.maze_map[i][j+1] == MazeBase.WALL:
                        wall_cnt += 1

                    #基本的に上下左右に壁が2つあったら通路とする
                    #ただしL字の場合はコーナーとする
                    if (wall_cnt != 2 or 
                    (wall_cnt == 2 and 
                    ((self.maze_map[i-1][j] == MazeBase.PATH and self.maze_map[i][j-1] == MazeBase.PATH) or 
                    (self.maze_map[i-1][j] == MazeBase.PATH and self.maze_map[i][j+1] == MazeBase.PATH) or
                    (self.maze_map[i+1][j] == MazeBase.PATH and self.maze_map[i][j-1] == MazeBase.PATH) or
                    (self.maze_map[i+1][j] == MazeBase.PATH and self.maze_map[i][j+1] == MazeBase.PATH)))):
                        conner_points.append(ConnerPoint(conner_no, j, i))
                        conner_no += 1

        print(conner_points)
        self.conner_points = conner_points

    def create_conner_network(self):
        state_inf_dic = {}
        for conner in self.conner_points:
            base_i = conner.y
            base_j = conner.x
            west = None
            north = None
            east = None
            south = None

            for j in range(base_j-1, 0, -1):
                if self.maze_map[base_i][j] == MazeBase.WALL:
                    break
                
                no = self._exist_pos(j, base_i)
                if no > 0:
                    west = no
                    break

            for i in range(base_i-1, 0, -1):
                if self.maze_map[i][base_j] == MazeBase.WALL:
                    break
                
                no = self._exist_pos(base_j, i)
                if no > 0:
                    north = no
                    break 

            for j in range(base_j+1, self.width):
                if self.maze_map[base_i][j] == MazeBase.WALL:
                    break
                
                no = self._exist_pos(j, base_i)
                if no > 0:
                    east = no
                    break

            for i in range(base_i+1, self.height):
                if self.maze_map[i][base_j] == MazeBase.WALL:
                    break
                
                no = self._exist_pos(base_j, i)
                if no > 0:
                    south = no
                    break
            state_inf_dic[State(conner.y, conner.x)] = StateInfo(conner.no, west, north, east, south)
            print("{} : {}, {}, {}, {}".format(conner.no, west, north, east, south))
        self.state_inf_dic = state_inf_dic

    def _exist_pos(self, x, y):
        for conner in self.conner_points:
            if conner.x == x and conner.y == y:
                return conner.no
        return 0

    def _set_start_goal(self):
        self.start_point = self.conner_points[0]
        self.goal_point = self._search_longest_distance_Point(self.start_point, self.conner_points, self.state_inf_dic)[0]
        self.maze_map[self.start_point.y][self.start_point.x] = MazeBase.START
        self.maze_map[self.goal_point.y][self.goal_point.x] = MazeBase.GOAL

    def print_maze(self):
        for row in self.maze_map:
            for cell in row:
                if cell == MazeBase.PATH:
                    print('   ', end='')
                elif cell == MazeBase.START:
                    print(' S ', end='')
                elif cell == MazeBase.GOAL:
                    print(' G ', end='')
                elif cell == MazeBase.WALL:
                    print('###', end='')
            print()