[BOJ]4179-火!

37249 ワード
DFS/BFS アルゴリズム#アルゴリズム# boj テキストリンク

質問リンク


火!

問題の説明


R*Cサイズの迷宮.迷宮の各格子は空で、智勲の位置、火の位置、壁の位置です.智勲は毎秒水平/垂直方向に移動し、火は毎秒4方向に拡散する.智勲が火に焼かれる前に脱出できるかどうか、できればどれだけ早く脱出できるかを求めます!

問題を解く


試してみる。


i秒火の拡散位置を知る.迷路で値を直接操作すると複雑になる可能性があるので、火の座標を格納するfireリストを作成しました.
Fire[i]:i秒後に拡散した火座標を保存する
bfsを回すときはt秒で智勲の移動を実行します.
  • 先拡散火(t+1秒の結果)
  • 智勲は移動可能な4方向の壁ではなく、拡散していない火を列に入れた.
    • でも7%が時間を超えて^ㅠ、
    import sys
from collections import deque
import copy

input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

R, C = map(int, input().split())
maze = []
jihoon = []
fire = [[]]

for i in range(R):
    tmp = list(input().strip())
    for j in range(C):
        if tmp[j] == 'J':
            jihoon = [i,j]
            tmp[j] = '.'
        elif tmp[j] == 'F':
            fire[0].append((i,j))
            tmp[j] = '.'
    maze.append(tmp)

def in_range(x, y):
    if x in range(R) and y in range(C):
        return True
    return False

def move_fire():
    tmp = set()
    for x, y in fire[-1]:
        for i in range(4):
            fx, fy = x+dx[i], y+dy[i]
            if in_range(fx, fy) and maze[fx][fy] != '#':
                tmp.add((fx, fy))
            tmp.add((x, y))
    fire.append(list(tmp))

def bfs(x, y):
    queue = deque([[x, y, 0]])
    visited = [[0]*C for _ in range(R)]
    visited[x][y] = 1

    while queue:
        x, y, time = queue.popleft()

        if x == 0 or x == R-1 or y == 0 or y == C-1:
            return time+1
        
        if len(fire) == time+1:
            move_fire()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_range(nx, ny) and visited[nx][ny] == 0 and maze[nx][ny] == '.' and (nx, ny) not in fire[time+1]:
                queue.append([nx, ny, time+1])
                visited[nx][ny] = 1
    return -1

answer = bfs(jihoon[0], jihoon[1])
if answer == -1:
    print("IMPOSSIBLE")
else:
    print(answer)

    試してみる。


    火の列と智勲は列を作り、bfsをそれぞれ返した.
    尋問の基準を智勲に定める.
    拡散
  • 火
  • 智勲を移す.
    ->4方向にスペースがある場合はqueueを入れます.
    • 移動時にfor文をfor _ in range(len(jihoon)):に変換し、t秒での移動のみを計算するため、別途時間を記憶する必要はない.
    def bfs():
    time = 0
    while jihoon:
        #불 확산시키기
        for _ in range(len(fire)):
            x, y = fire.popleft()
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if in_range(nx, ny) and (maze[nx][ny] == '.' or maze[nx][ny] == 'J') :
                    maze[nx][ny] = 'F'
                    fire.append((nx,ny))

        #지훈이 이동
        for _ in range(len(jihoon)):
            x, y = jihoon.popleft()
            if x == 0 or x == R-1 or y == 0 or y == C-1:
                return time+1
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if in_range(nx, ny) and maze[nx][ny] == '.':
                    maze[nx][ny] = 'J'
                    jihoon.append((nx, ny))
        time += 1
    return -1

    完全なコード

    import sys
from collections import deque
import copy

input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

R, C = map(int, input().split())
maze = []
jihoon = deque()
fire = deque()

for i in range(R):
    tmp = list(input().strip())
    for j in range(C):
        if tmp[j] == 'J':
            jihoon.append((i,j))
        elif tmp[j] == 'F':
            fire.append((i,j))
    maze.append(tmp)

def in_range(x, y):
    if x in range(R) and y in range(C):
        return True
    return False

# fire[i] : i초 뒤 불의 확산좌표들 저장
def move_fire():
    tmp = set()
    for x, y in fire[-1]:
        for i in range(4):
            fx, fy = x+dx[i], y+dy[i]
            if in_range(fx, fy) and maze[fx][fy] != '#':
                tmp.add((fx, fy))
            tmp.add((x, y))
    fire.append(list(tmp))

def bfs():
    time = 0
    while jihoon:
        #불 확산시키기
        for _ in range(len(fire)):
            x, y = fire.popleft()
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if in_range(nx, ny) and (maze[nx][ny] == '.' or maze[nx][ny] == 'J') :
                    maze[nx][ny] = 'F'
                    fire.append((nx,ny))

        #지훈이 이동
        for _ in range(len(jihoon)):
            x, y = jihoon.popleft()
            if x == 0 or x == R-1 or y == 0 or y == C-1:
                return time+1
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if in_range(nx, ny) and maze[nx][ny] == '.':
                    maze[nx][ny] = 'J'
                    jihoon.append((nx, ny))
        time += 1
    return -1

answer = bfs()
if answer == -1:
    print("IMPOSSIBLE")
else:
    print(answer)

    に感銘を与える


    この間bfsを使った問題は私が指定したテンプレートで解決したもので、問題によっては柔軟に変更できるはずです.例えば、2つのキューを作成し、、、、時間を保存せずにその時間内に可能な移動を一度に処理し、

    困難な人
    Java (5)
    stream、string、byte[]相互回転