質問リンク

大人のサメ

問題の説明

1番からM番の間の番号はM匹のサメがN*Nグラム街の格子にいます.初期には、すべてのサメが自分の位置でにおいを放つ.
1秒あたりの移動

すべてのサメが上下左右に隣接する格子に移動してにおいを放つ.

サメがK回移動した後(k秒後)においが消えた.

・먽먽・移動後、一格に複数のサメがいて、一番小さい番号のサメだけが生き残る
移動方向は、1、2、3、4、右と定義されます.隣接するセルに移動する方向は、次のとおりです.

隣の4部屋の中で何のにおいもしない部屋

1番は満足のいく格子がなく、においのある格子

に移動します.満たされたセルが複数ある場合は、与えられた各方向の特定の優先度を入力します.
サメの頭の方向は、初期は入力と同じで、その後は移動方向に見える方向です.
各サメの位置、向き、および各サメの移動優先度を入力します.

5 4 4 // N M k
0 0 0 0 3
0 2 0 0 0
1 0 0 0 4
0 0 0 0 0
0 0 0 0 0 // 격자위 상어들의 위치
4 4 3 1 // 상어들의 초기 바라보는 방향
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2 // 상어 1의 상-하-좌-우 바라볼때의 이동 우선순위 
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3 // 상어 2의 상-하-좌-우 바라볼때의 이동 우선순위 
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4 // 상어 3의 상-하-좌-우 바라볼때의 이동 우선순위 
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3 // 상어 4의 상-하-좌-우 바라볼때의 이동 우선순위 

この時、サメが1番しか残っていないのはどのくらいかかりますか?

問題を解く

入力が非常に長く、非常に多く、デバッグが難しいように見えたので、一気に解くために、水道コードをできるだけ丁寧に書いてコードに移動しました.

入力の受信

サメの位置と味smell[i][j]:(i,j)格の[サメ番号、におい残り時間]shark[i][j]:(i,j)格のサメ番号保存->一つの格に複数のサメがいるかチェックするshark[k]:[d,(x,y)]と共にk号サメをd方向報告(x,y)に貯蔵するディクシャナリー
図示のように、ほぼ3つのリストと1つのディックシャナリストが保存されています.
各サメは観察方向の優先順位によって以下の通りである.priority[k][d]:k号サメがd方向を望む場合の優先順位

smell = [[0 for _ in range(N)] for _ in range(N)] # smell[i][j] = [상어번호, 남은시간]
shark = [[[] for _ in range(N)] for _ in range(N)] # shark[i][j] = [k] : (i,j)에 현재 k번 상어있음 -> 한칸에 여러 상어 있는지 검사용
sharks = {} # shark[k] = [d, (x,y)] : k번 상어가 d 방향 보고 (x,y)에 위치
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(N):
        if tmp[j] != 0:
            shark[i][j].append(tmp[j])
            sharks[tmp[j]] = [(i,j)]
            smell[i][j] = [tmp[j], K] #초기 냄새, 시간 퍼뜨리기

direction = list(map(int, input().split()))
for i in range(M):
    sharks[i+1].append(direction[i])

priority = defaultdict(list) # priority[k][d] : k번 상어의 방향 d 우선순위
for i in range(M):
    for j in range(4):
        # i번 상어의 각 네방향 마다의 우선순위
        priority[i+1].append(list(map(int, input().split())))

1秒あたりの移動

1秒あたりの移動

優先順位でサメを隣接格に移動

    for s in sharks.keys():
        (x, y), d = sharks[s]
        count_empty = [] # 빈칸 count
        count_me = [] # 내 냄새가 있는 칸
        # 4방향 검사하기
        for i in range(1, 5):
            nx, ny = x+dx[i], y+dy[i]
            if in_range(nx, ny):
                # 빈칸 count
                if smell[nx][ny] == 0:
                    count_empty.append(i)
                # 내 냄새가 있는 칸인지 count
                elif smell[nx][ny][0] == s:
                    count_me.append(i)
        
        if len(count_empty) == 1:
            # 해당 칸으로 이동하기
            shark[x][y].remove(s)
            shark[x+dx[count_empty[0]]][y+dy[count_empty[0]]].append(s)
            sharks[s] = [(x+dx[count_empty[0]],y+dy[count_empty[0]]), count_empty[0]]
        elif len(count_empty) > 1:
            # 우선순위에 따라 이동하기 -> priority[k][d] : k번 상어의 d번 priority에 따라
            for p in priority[s][d-1]:
                if p in count_empty:
                    # 해당 방향으로 이동
                    shark[x][y].remove(s)
                    shark[x+dx[p]][y+dy[p]].append(s)
                    sharks[s] = [(x+dx[p],y+dy[p]), p]
                    break

        elif len(count_me) == 1:
            # 해당 칸으로 이동하기
            shark[x][y].remove(s)
            shark[x+dx[count_me[0]]][y+dy[count_me[0]]].append(s)
            sharks[s] = [(x+dx[count_me[0]],y+dy[count_me[0]]), count_me[0]]
        elif len(count_me) > 1:
            # 우선순위에 따라 이동하기 -> priority[k][d] : k번 상어의 d번 priority에 따라
            for p in priority[s][d-1]:
                if p in count_me:
                    # 해당 방향으로 이동
                    shark[x][y].remove(s)
                    shark[x+dx[p]][y+dy[p]].append(s)
                    sharks[s] = [(x+dx[p],y+dy[p]), p]
                    break

重ねたハーモニーが長すぎて….重なる部分は単独で関数で表すとより簡潔になります.

1マスに複数のサメがいるかチェックして駆逐
:2本以上の格子を昇順に並べ、番号が一番小さいサメを除いて、すべて送り出します.

    for i in range(N):
        for j in range(N):
            if len(shark[i][j]) > 1:
                shark[i][j].sort()
                # 제일 번호 작은 상어 빼고 다 내보내기
                del_shark = shark[i][j][1:]
                for s in del_shark:
                    (x, y), d = sharks[s]
                    shark[x][y].remove(s)
                    del(sharks[s])
                    n_shark -= 1

1マスあたりのにおい残り時間-=1

    for i in range(N):
        for j in range(N):
            if smell[i][j] != 0:
                if smell[i][j][1] == 1:
                    smell[i][j] = 0
                else:
                    smell[i][j][1] -= 1

移動している部屋ににおいがする

    for s in sharks.keys():
        (x, y), d = sharks[s]
        smell[x][y] = [s, K]

の順で体現する.

完全なコード

コード全体を以下に示します.

import sys
from collections import deque, defaultdict

input = sys.stdin.readline

dx = [0, -1, 1, 0, 0] # 상1하2좌3우4
dy = [0, 0, 0, -1, 1]

N, M, K = map(int, input().split())
n_shark = M
def in_range(x, y):
    if x in range(N) and y in range(N):
        return True
    return False

smell = [[0 for _ in range(N)] for _ in range(N)] # smell[i][j] = [상어번호, 남은시간]
shark = [[[] for _ in range(N)] for _ in range(N)] # shark[i][j] = [k] : (i,j)에 현재 k번 상어있음 -> 한칸에 여러 상어 있는지 검사용
sharks = {} # shark[k] = [d, (x,y)] : k번 상어가 d 방향 보고 (x,y)에 위치
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(N):
        if tmp[j] != 0:
            shark[i][j].append(tmp[j])
            sharks[tmp[j]] = [(i,j)]
            smell[i][j] = [tmp[j], K] #초기 냄새, 시간 퍼뜨리기

direction = list(map(int, input().split()))
for i in range(M):
    sharks[i+1].append(direction[i])

priority = defaultdict(list) # priority[k][d] : k번 상어의 방향 d 우선순위
for i in range(M):
    for j in range(4):
        # i번 상어의 각 네방향 마다의 우선순위
        priority[i+1].append(list(map(int, input().split())))

time = 0
# 매초마다의 동작
while True:
    if n_shark == 1:
        print(time)
        break
    if time >= 1000:
        print(-1)
        break
    
    # 모든 상어 이동
    for s in sharks.keys():
        (x, y), d = sharks[s]
        count_empty = [] # 빈칸 count
        count_me = [] # 내 냄새가 있는 칸
        # 4방향 검사하기
        for i in range(1, 5):
            nx, ny = x+dx[i], y+dy[i]
            if in_range(nx, ny):
                # 빈칸 count
                if smell[nx][ny] == 0:
                    count_empty.append(i)
                # 내 냄새가 있는 칸인지 count
                elif smell[nx][ny][0] == s:
                    count_me.append(i)
        
        if len(count_empty) == 1:
            # 해당 칸으로 이동하기
            shark[x][y].remove(s)
            shark[x+dx[count_empty[0]]][y+dy[count_empty[0]]].append(s)
            sharks[s] = [(x+dx[count_empty[0]],y+dy[count_empty[0]]), count_empty[0]]
        elif len(count_empty) > 1:
            # 우선순위에 따라 이동하기 -> priority[k][d] : k번 상어의 d번 priority에 따라
            for p in priority[s][d-1]:
                if p in count_empty:
                    # 해당 방향으로 이동
                    shark[x][y].remove(s)
                    shark[x+dx[p]][y+dy[p]].append(s)
                    sharks[s] = [(x+dx[p],y+dy[p]), p]
                    break

        elif len(count_me) == 1:
            # 해당 칸으로 이동하기
            shark[x][y].remove(s)
            shark[x+dx[count_me[0]]][y+dy[count_me[0]]].append(s)
            sharks[s] = [(x+dx[count_me[0]],y+dy[count_me[0]]), count_me[0]]
        elif len(count_me) > 1:
            # 우선순위에 따라 이동하기 -> priority[k][d] : k번 상어의 d번 priority에 따라
            for p in priority[s][d-1]:
                if p in count_me:
                    # 해당 방향으로 이동
                    shark[x][y].remove(s)
                    shark[x+dx[p]][y+dy[p]].append(s)
                    sharks[s] = [(x+dx[p],y+dy[p]), p]
                    break
    
    # 한칸에 여러 상어 있는지?
    for i in range(N):
        for j in range(N):
            if len(shark[i][j]) > 1:
                shark[i][j].sort()
                # 제일 번호 작은 상어 빼고 다 내보내기
                del_shark = shark[i][j][1:]
                for s in del_shark:
                    (x, y), d = sharks[s]
                    shark[x][y].remove(s)
                    del(sharks[s])
                    n_shark -= 1

    # 남은시간 -= 1
    for i in range(N):
        for j in range(N):
            if smell[i][j] != 0:
                if smell[i][j][1] == 1:
                    smell[i][j] = 0
                else:
                    smell[i][j][1] -= 1

    # 냄새 뿌리기
    for s in sharks.keys():
        (x, y), d = sharks[s]
        smell[x][y] = [s, K]
    
    time += 1

最初は勘違いしていた部分.
1.時間が1000秒、格子にサメが1匹しかいないとき
->このとき1000が正解です.
2.撃つときにリストを削除、、、これは毎回混同されます^ㅠ

入力が長すぎて、シミュレーションの過程が複雑すぎて、最初は間違っていて、出てきてから迷っています...間違ったところはすぐに見つけて修正しました^^;

所要時間

2時間!