やりとちゅう

tmp.py

class ArcadeManao:
    def shortestLadder(self, level, coinRow, coinColumn):
        self.level = level
        self.goal = (coinRow - 1, coinColumn - 1)

        N = len(level) - 1
        M = len(level[0]) - 1
        print ((N, M), level[N][M])
        for ladder_len in xrange(0, N+1):
            print ('--start--', ladder_len)
            queue = []
            visited = set()
            for m in xrange(M + 1):
                if self.add2queue(N, m, queue, visited):
                    return ladder_len

            while queue:
                q = queue.pop(0)
                visited.add(q)

                for r in xrange(-ladder_len, ladder_len):
                    if q[0] + r > M or q[0] + r < 0:
                        continue

                    for right in xrange(q[1], M+1):
                        if level[q[0]][right] != 'X':
                            break
                        if self.add2queue(q[0] + r, right, queue, visited):
                            return ladder_len
                    reversed(range(0, q[1]))
                    for left in reversed(range(0, q[1])):
                        if level[q[0]][left] != 'X':
                            break
                        if self.add2queue(q[0] + r, left, queue, visited):
                            return ladder_len
        return -1

    def add2queue(self, r, c, queue, visited):
        print ((r, c), self.level[r][c])
        if self.level[r][c] != 'X':
            return False
        if (r, c) == self.goal:
            return True
        if (r, c) not in visited and (r, c) not in queue:
            queue.append((r, c))
            return False
        return False