[ノート/python]アップグレードコード-CAdy Fang

質問する

解けなかった理由

BFSアルゴリズムを使用して、現在のセルに上下左右同じ色のセルがあるかどうかを確認してみますが、現在のセルと同じセルのバンドルを計算する方法が分かりません.

に答える

BFSアルゴリズムを用いて現在のセルから上下左右を決定し,同じ色があれば再びそのセルから上下左右を決定する.このように計算された1つの格が3つを超えると、爆発した領域とみなされます.

board = []
for _ in range(7):
    board.append(list(map(int, input().split())))

from collections import deque

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

def bfs(x, y, board, visited):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True    # 방문 처리

    color = board[x][y]    # 현재 칸의 색상
    count = 1    # 같은 색의 칸 개수

    # 큐가 빌 때까지 반복
    while queue:
        x, y = queue.popleft()

        # 현재 칸에서 상하좌우 확인
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            # 보드 넘어서면 무시하기
            if nx < 0 or nx >= 7 or ny < 0 or ny >= 7:
                continue

            # 칸의 색상이 동일하고 방문한 적 없으면 재귀 (그 칸을 기준으로 다시 상하좌우 확인)
            if board[nx][ny] == color and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True    # 방문처리
                count += 1

    # 색상이 같은 부분이 3개 이상이면
    if count >= 3:
        return True
    else:
        return False

visited = [[False for _ in range(7) ] for _ in range(7)]    # 방문 여부
res = 0    # 터지는 영역의 개수

for i in range(7):
    for j in range(7):
        if not visited[i][j]:
            if bfs(i, j, board, visited):
                res += 1

print(res)

上のコードをよく見てみましょう.
まず,BFSアルゴリズムを用いるためにdequeを導入する.次に、座標を定義して、上下左右のセルを決定します.

from collections import deque

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

次に、一番下の部分から、各セルにアクセスするかどうかの2 Dリストを記録し、最終的に爆発領域の数を含むres変数を与えます.
2重forゲートで各格子を確認します.bfs関数の結果はTrueまたはFalseであり、同じ色のセルが3つ以上ある場合はTrueまたはFalseを返します.

visited = [[False for _ in range(7) ] for _ in range(7)]    # 방문 여부
res = 0    # 터지는 영역의 개수

for i in range(7):
    for j in range(7):
        if not visited[i][j]:
            if bfs(i, j, board, visited):
                res += 1

print(res)

bfs関数を見てみましょう.まず、現在アクセスしているセルをキューに入れ、アクセスするかどうかをTrueに更新します.次に、現在のセルの色と同じ色のセル数変数を定義します.
今Q求まで繰り返します.
まず、現在のセルの座標(x,y)をキューから取り出します.この座標を基準に上下左右の格を確認し、まだアクセスしておらず色が同じ格の場合のみその格を基準に上下左右を確認します.(count += 1)
このように確認した後、同じ色のセルが3つを超えると、TrueまたはFalseを返します.

def bfs(x, y, board, visited):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True    # 방문 처리

    color = board[x][y]    # 현재 칸의 색상
    count = 1    # 같은 색의 칸 개수

    # 큐가 빌 때까지 반복
    while queue:
        x, y = queue.popleft()

        # 현재 칸에서 상하좌우 확인
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            # 보드 넘어서면 무시하기
            if nx < 0 or nx >= 7 or ny < 0 or ny >= 7:
                continue

            # 칸의 색상이 동일하고 방문한 적 없으면 재귀 (그 칸을 기준으로 다시 상하좌우 확인)
            if board[nx][ny] == color and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True    # 방문처리
                count += 1

    # 색상이 같은 부분이 3개 이상이면
    if count >= 3:
        return True
    else:
        return False

振り返る

確かに,BFSアルゴリズムを用いた基本コード(ベースコード)は以前に比べてよく記述されているが,問題に適したコードを記述することはまだ困難である.もっと頑張りましょう.