[BOJ/Python]16234番人口移動

11656 ワード
サムスン python BFS boj テキストリンク

今回の問題は三星の寄付問題で、BFSが開放したすべての国境線を通じて、現在位置している国と関係のあるすべての国を救い、これらの国の人口数を平均値に更新することだ.この過程を経る前の国全体の人口状況を貯蔵し、その過程を経た後の人口状況と比較し、両者は同じ時に繰り返し行われる.
  • n,l,rと入力します.
    • 入力
  • 接地.
  • dy,dxは4方向を格納する.
  • bfs関数をsy、sxとしてパラメータとして宣言します.
    ->qはdequeです.
    ->qに(sy, sx)を入れます.
    ->visited[sy][sx]が1に更新されました.
    ->関連国の人口を格納する変数の総数をground[sy][sx]とする.
    ->接続先のリストcntを保存し、(sy,sx)を宣言します.
    ->qが存在する場合は繰り返し、ドアを回します.
    -->qはy,xを抽出する.
    -->4回繰り返したiに対してfor文を回します.
    ----->宣言ny,nxはy+dy[i],x+dx[i]であった.
    -->ny、nxが0より大きくnより小さい場合、visited[ny][nx]が0ground[y][x]-ground[ny][nx]の節気値がlより大きく、r以下である場合、
    ------>visited[ny][nx]が1に更新されました.
    ------>合計ground[ny][nx].
    ------>cntに(ny, nx)を加えます.
    ------>qに(ny, nx)を入れます.
    ->巡回cntに関するi,jのfor文.
    -->ground[i][j]がtotal//len(cnt)に更新されました.
  • 回答は0です.
  • を繰り返しながらドアを回します.
    ->tmpでdeepcopy groundを保存します.
    ->アクセス処理リストは、アクセス量をn*nサイズとして宣言し、0を入力します.
    ->n対iを繰り返すfor文.
    -->n対jのfor文を繰り返す.
    ----->visited[i][j]が0の場合、
    ---->bfs(i, j).
    ->tmpが地面と異なる場合、
    -->答えを1つ増やします.
    ->その他の場合、
    -->whileドアを出ます.
  • の回答を印刷します.

    • Code

    from collections import deque
from copy import deepcopy
n, l, r=map(int, input().split())
ground=[list(map(int, input().split())) for _ in range(n)]
dy, dx=[1, 0, -1, 0], [0, 1, 0, -1]
def bfs(sy, sx):
    q=deque()
    q.append((sy, sx))
    visited[sy][sx]=1
    total=ground[sy][sx]
    cnt=[(sy, sx)]
    while q:
        y, x=q.popleft()
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<n and 0<=nx<n and not visited[ny][nx] and l<=abs(ground[y][x]-ground[ny][nx])<=r:
                visited[ny][nx]=1
                total+=ground[ny][nx]
                cnt.append((ny, nx))
                q.append((ny, nx))
    for i, j in cnt:
        ground[i][j]=total//len(cnt)
answer=0
while True:
    tmp=deepcopy(ground)
    visited = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                bfs(i, j)
    if tmp!=ground:
        answer+=1
    else:
        break
print(answer)
    SEALライブラリテスト効率(例6の6_performance解析)
    webserviceはsoapUIで日付フォーマットをテストして入力します