ABC151_D(Maze Master)

問題

• AtCoder Beginner Contest 151- D

考えたこと

• オーダの制約が 20 * 20 = 4,000 =
• これなら 以内に収まるので全パターンで幅優先探索でOK
  • と思っていたらどうしてもTLEが取れない！なんで！？となりました

実装(TLE版)

from collections import deque
 
h, w = [int(x) for x in input().split()]
 
maze = []
 
for y in range(h+2):
    if y == 0 or y == h+1:
        maze.append([1 for x in range(w+2)])
    else:
        line = [1]
        for x, c in enumerate(input(), 1):
            if c == "#":
                line.append(1)
            else:
                line.append(0)
        line.append(1)
        maze.append(line)
 
 
def solve(queue, maze):
    end = set()
    max_point = 0
 
    while queue:
        x, y, point = queue.pop()
 
        end.add((x, y)) # ★ここが遅くなっている理由です
        max_point = max(max_point, point)
 
        if maze[y+1][x] == 0:
            if not (x, y+1) in end:
                queue.appendleft((x, y+1, point+1))
 
        if maze[y-1][x] == 0:
            if not (x, y-1) in end:
                queue.appendleft((x, y-1, point+1))
 
        if maze[y][x+1] == 0:
            if not (x+1, y) in end:
                queue.appendleft((x+1, y, point+1))
 
        if maze[y][x-1] == 0:
            if not (x-1, y) in end:
                queue.appendleft((x-1, y, point+1))
 
    return max_point
 
 
max_count = 0
for y in range(1, h+1):
    for x in range(1, w+1):
        if maze[y][x] == 0:
            queue = deque()
            queue.appendleft((x, y, 0))
            max_count = max(max_count, solve(queue, maze))
 
print(max_count)

何が悪かったのか

• 今まで幅優先探索では, 目的を見つけたら break して処理を終了させていることが多かった
• 今回の問題の場合, 最後まで処理を回さないと答えが分からない類の問題であったため, 処理を打ち切っていない
  • 当該ノードに移動することが確定した時点で, 処理済フラグを立てておけばよかった

ABC151_D_良い例と悪い例

最終的にできた実装(色々とこねくり回した版)

from collections import deque
 
h, w = [int(x) for x in input().split()]
check = [(0, 1), (0, -1), (1, 0), (-1, 0)]
 
maze = []
 
for y in range(h+2):
    if y == 0 or y == h+1:
        maze.append([1 for x in range(w+2)])
    else:
        line = [1]
        for x, c in enumerate(input(), 1):
            if c == "#":
                line.append(1)
            else:
                line.append(0)
        line.append(1)
        maze.append(line)
 
max_count = 0
 
 
def solve(x, y):
    queue = deque()
    queue.append((x, y))
 
    end = [[-1 for _ in range(w+2)] for _ in range(h+2)]
    end[y][x] = 0
 
    max_count = 0
    while queue:
        now_x, now_y = queue.popleft()
        max_count = max(max_count, end[now_y][now_x])
 
        for tx, ty in check:
            next_x = now_x + tx
            next_y = now_y + ty
            if maze[next_y][next_x] == 0 and end[next_y][next_x] == -1:
                end[next_y][next_x] = end[now_y][now_x] + 1
                queue.append((next_x, next_y))
 
    return max_count
 
 
max_count = 0
for y in range(1, h+1):
    for x in range(1, w+1):
        if maze[y][x] == 0:
            max_count = max(max_count, solve(x, y))
 
 
print(max_count)

結果

• 無事に AC できました
• kernprof の 使い方や読み方もなんとなく覚える事ができたので結果的には良しとする