BOJ 2146ブリッジの作成

https://www.acmicpc.net/problem/2146
時間2秒、メモリ192 MB
input :

N(1 <= N <= 100)

Nの数字(0は海、1は陸地)

output :

出力最短ブリッジ長

条件:

この国は複数の島からなり、島とは東西南北の陸地が連なるブロック

を指す.
初めて近づいた時.
私たちはまずBFSで島を並べ替えます.
2, 3, 4 .....
そして、島の端の部分を列に入れます.
BFSを実行し、最初に別の島に到着した場合、切断して出力します.
queueが無限に増加したためか、メモリが超過しています.やれやれ...
他人の解答を見て、改善すべきところを探します.

島の枠部分をキューに入れたとき.これ以上繰り返さないで、グループ分けの時に分類しましょう.

            elif graph[nx][ny] == 0 and not (now_x, now_y, 0) in queue:
                queue.append((now_x, now_y, 0))

(nx,ny)が島の外、すなわち海であれば、現在存在する(now x,now y)をキューに入れ、距離を0と表す.
in methodで重複を生じないでください.

距離を求める時

上、下、左、右の島番号を実行します.
島番号**より小さい場合**
**さんはどういう意味ですか.
Qが出した島号の存在順.
2,3,4の順序でキューに入れると、キューから削除し直すときも順序が保たれます.

すでにBFSが実行されており、2人の島は1つの距離を増やした.
ここに4人の島がBFSを実行している場合、4가 들어와야 함位に達します.
この場合、距離を求めるには(cnt + 1) * 2 - 1を計算します.
隣接する島の番号より大きい場合.

島番号が4の場合、実行BFSは5と出会う.この場合、BFSを実行する前に見たことがあるが、(cnt) * 2を計算する必要がある.

        if graph[nx][ny] == 0:
            graph[nx][ny] = graph[x][y]
            queue.append((nx, ny, cnt + 1))

        elif graph[nx][ny] > graph[x][y]:
            dis = min(dis, cnt * 2)

        elif graph[nx][ny] < graph[x][y]:
            dis = min(dis, ((cnt + 1) * 2) - 1)

このBFSを1ラウンドずつ
1号/2号に分けられるような気がしたので火麟を入れて色々しました
結局これに時間がかかったので...今度アクセルを再利用しようか口だけで书くのはおかしい...

import sys
from _collections import deque

n = int(sys.stdin.readline())
graph = []

for i in range(n):
    data = list(map(int, sys.stdin.readline().split()))
    graph.append(data)

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def BFS(x, y, num):
    q = deque([(x, y)])
    graph[x][y] = num

    while q:
        now_x, now_y = q.popleft()
        for i in range(4):
            nx = now_x + dx[i]
            ny = now_y + dy[i]
            if nx >= n or nx < 0 or ny >= n or ny < 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = num
                q.append((nx, ny))
            elif graph[nx][ny] == 0 and not (now_x, now_y, 0) in queue:
                queue.append((now_x, now_y, 0))

cnt = 2
queue = deque()
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            BFS(i, j, cnt)
            cnt += 1

dis = 99999
while queue:
    done = False
    x, y, cnt = queue.popleft()
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx >= n or nx < 0 or ny >= n or ny < 0:
            continue

        if graph[nx][ny] == 0:
            graph[nx][ny] = graph[x][y]
            queue.append((nx, ny, cnt + 1))

        elif graph[nx][ny] > graph[x][y]:
            dis = min(dis, cnt * 2)

        elif graph[nx][ny] < graph[x][y]:
            dis = min(dis, ((cnt + 1) * 2) - 1)

print(dis)