質問する

笛を吹く男の漢勝宇は今日も笛を吹く.
聖佑が笛を吹くたびに、英和日の会員たちはいつの間にか聖佑が設定した方向に移動し始めた.声優が設定する方向はU、D、L、Rの4種類で、それぞれ上、下、左、右に移動する.
それを見ていたジェフンは、これ以上動けなくなった英和日会員たちを守るため、特定の場所に「SAFEZONE」という最先端の防音施設を建て、メンバーたちに声優の笛の音が聞こえないようにした.しかし予算が足りなかったジェフンは声優設定の方向性を分析し、最小限の数の『SAFEZONE』を作ろうとした.
声優が設定した方向図があれば、在勲、英和日の会員たちが地図のどのエリアでも、声優が笛を吹くときに「SAFEZONE」に入ることができる「SAFEZONE」の最低数のプログラムを書くのを手伝ってください.

に答える

本明細書の例を図に示す.(0,0)点を基準として矢印に沿って歩き続け、以下の周期を決定することができる.

ループが作成されると、そのループ内の任意の場所にセキュリティパーティションがインストールされ、最終的にはセキュリティパーティションに移動できます.
つまり、問題が要求する最終地図は何サイクルありますか?要約すると.
周期を決定する方法には分離セットアルゴリズムがあるので,本問題を分離セットに分解する.
まずfor文で各セルを1つずつ表示します.
ユニットとユニットが指すユニットが同じセットにあるかどうかをチェックし、同じセットにない場合は、同じセットに更新する方向にアルゴリズムを展開します.

コード#コード#

# 피리 부는 사나이
import sys
input = sys.stdin.readline

# 입력 받기
num_rows, num_cols = map(int, input().split())
board = [list(input().rstrip()) for _ in range(num_rows)] # 개행문자 제거

# 방향
dirs = {"D" : (1,0), "U"  : (-1,0), "L" : (0,-1), "R" : (0,1)}
parents = list(range(num_cols * num_rows))

# 어떻게 풀 것인가?
# 앞에서부터 하나씩 읽어가면서 union 업데이트
# 총 집합의 개수 찾기

def find_root(cell_id):
    stack = []

    while True:
        stack.append(cell_id)
        parent = parents[cell_id]

        if parent == cell_id:
            break
        else:
            cell_id = parent

    while stack:
        aux_cell = stack.pop()
        parents[aux_cell] = cell_id

    return cell_id
        
def union(root_a, root_b):

    if root_a < root_b:
        parents[root_b] = root_a
    else:
        parents[root_a] = root_b

def get_cell_id (i,j):
    return num_cols * i + j

def get_next_cell(i,j, dir): 
    d_row, d_col = dirs[dir]

    new_i = i + d_row
    new_j = j + d_col

    return new_i, new_j

for i in range(num_rows):
    for j in range(num_cols):

        cell = board[i][j] # 탐색을 진행하는 셀
        new_i, new_j = get_next_cell(i, j, cell) # 셀대로 갔을 때 다음 셀 관련 정보

        cell_id = get_cell_id(i,j)
        next_cell_id = get_cell_id(new_i, new_j)

        # 두 셀이 같은 집합에 속해있는지 파악
        root = find_root(cell_id)
        root_next = find_root(next_cell_id)

        #print(f"cell_id {cell_id}, next_cell_id {next_cell_id}, root {root}, root_next {root_next}")

        # 만약 두 셀이 같은 집합에 포함되지 않았다면
        if root != root_next:
            # 두 셀을 하나의 집합으로 넣는다. (어차피 다음 경로로 갈 것이기 때문)
            union(root, root_next)
            
result_set = set()
parents_set = set(parents)

for i in parents_set:
    root = find_root(i)
    result_set.add(root)

print(len(result_set))

一部のセルのルートは、参照時にのみ最新のルートに更新されます.
したがって、1回のみ参照されるセルは最新のルートに更新されないため、最後に最新のルートに更新すると最終ループの数が検索されます.