[BOJ/Python]16236号サメ

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

この問題はBFSを利用して条件に合った空間の中の位置に移動し,二度と移動できなくなるまで繰り返される.答えを探したり、答えを出したりするのに時間がかかったが、多くの問題が得られた.
  • nと入力します.
  • 空間をgridに入力します.
    • サメの位置を表す変数cur y,cur xは0である.
  • n回繰り返したiに対してfor文を行う.
    ->n対jを繰り返すfor文.
    -->grid[i][j]が9の場合、
    ----->cur y,cur xをi,jに更新する.
    ----->grid[i][j]を0に更新します.
    句を终える.
  • 赤ちゃんサメの大きさの変数babyは2です.
  • 方向に対応するリストdy,dxは、上、左、右、下の順に記憶される.
  • bfs関数をcur yとして宣言し、cur xをパラメータとして使用します.
    ->qはdequeです.
    ->qに(0,cur y,cur x,0)を加えます.
    ->アクセス処理リストをn*nのサイズとして宣言し、Falseを埋めます.
    ->アクセスした[cur y][cur x]をtrueに更新します.
    ->食べられる魚の保存先のリスト結果をリストします.
    ->qが存在する場合、whileゲートを繰り返します.
    -->d,y,x,flgはqから抽出される.
    -->システムは最小距離の変数mdを格納する.maxsizeと宣言します.
    -->flgが1の場合、dがmd以下の場合、
    -->mdをdに更新します.
    -->結果に(d,y,x)を加えます.
    -->4回繰り返したiに対してfor文を回します.
    ----->ny,nxをy+dy[i],x+dx[i]に更新する.
    -->nyが0より大きく、nより小さく、nxが0より大きく、nより小さく、アクセス[ny][nx]がfalseの場合
    ------>grid[ny][nx]が0より大きくbabyより小さい場合、
    ------>アクセスした[ny][nx]をtrueに更新します.
    ------->qに(d+1,ny,nx,1)を加える.
    ------>grid[ny][nx]がbabyに等しい場合、またはgrid[ny][nx]が0である場合.
    ------>アクセスした[ny][nx]をtrueに更新します.
    ------->qに(d+1,ny,nx,0)を加える.
    ->結果が空の場合、
    -->[1,1,1,1].
    ->結果を昇順に並べます.
    ->結果[0]を返します.
  • の結果を保存した変数の答えを0と宣言します.
  • カウント変数cntはゼロです.
    • ドアを回すと
  • になります.
    ->time,cur y,cur xをbfs(cur y,cur x)として格納する.
    ->[time,cur y,cur x]が[1,1,1,1]に等しい場合、
    -->答えを印刷します.
    -->while文を閉じます.
    回答に時間をかける.
    ->grid[cur y][cur x]を0と宣言します.
    ->cnt 1を増やします.
    ->cntがbabyと同じ場合、
    -->baby 1を増やします.
    -->cntを0に更新します.

    • Code

    import sys
from collections import deque
n=int(input())
grid=[list(map(int, input().split())) for _ in range(n)]
cur_y, cur_x=0, 0
for i in range(n):
    for j in range(n):
        if grid[i][j]==9:
            cur_y, cur_x=i, j
            grid[i][j]=0
            break
baby=2
dy, dx=[-1, 0, 0, 1], [0, -1, 1, 0]
def bfs(cur_y, cur_x):
    q=deque()
    q.append((0, cur_y, cur_x, 0))
    visited=[[False]*n for _ in range(n)]
    visited[cur_y][cur_x]=True
    results=[]
    while q:
        d, y, x, flg=q.popleft()
        md=sys.maxsize
        if flg==1 and md>=d:
            md=d
            results.append((d, y, x))
        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]:
                if 0<grid[ny][nx]<baby:
                    visited[ny][nx]=True
                    q.append((d+1, ny, nx, 1))
                elif grid[ny][nx]==baby or grid[ny][nx]==0:
                    visited[ny][nx]=True
                    q.append((d+1, ny, nx, 0))
    if not results:
        return [-1, -1, -1]
    results.sort(key=lambda x: (x[0], x[1], x[2]))
    return results[0]
answer=0
cnt=0
while True:
    time, cur_y, cur_x=bfs(cur_y, cur_x)
    if [time, cur_y, cur_x]==[-1, -1, -1]:
        print(answer)
        break
    answer+=time
    grid[cur_y][cur_x]=0
    cnt+=1
    if cnt==baby:
        baby+=1
        cnt=0
    UNNotificationServiceExtension
    JMS test