BOJ 14716バナー

9031 ワード
2020.12.25 テキストリンク
https://www.acmicpc.net/problem/14716
2秒、512 MBメモリ
input :
  • M Nは、スペースで区切られている(1<=M,N<=250)
    • .
  • 0入力0の情報
    • output :
  • 文字の出力
    • 条件:
    第1部
  • 文字、文字でない場合024579182
  • 1の位置で、上、下、左、右、対角線が隣接する、互いに接続すると、一字
    • となる.
    上下左右のベクトル.
    y = [-1, 1, 0, 0]
    x = [0, 0, -1, 1]
    対角線のベクトル(上、上、下、下)
    y = [-1, -1, 1, 1]
    x = [-1, 1, -1, 1]
    一番上から2 Dリストを回転し、ポイントを見つけてBFSに入れます.
    これを0に変更します.
    そして上のベクトルの場合をすべて入れ、1に遭遇するとキューに追加します.
    BFS終了後に文字数を1文字上げる方式.
    -->BFSでのアクセスはエラーです.タイムアウトメモリの過剰運転時に三位一体の攻撃を受ける.
    DFSで解いてみます.
    条件文も変更する必要がある場合.
            if 0 <= x <= M and 0 <= y <= N and graph[nx][ny]:
            dfs(nx, ny)
    時間的にメリットがあるようだと判断した.
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
            continue
    再帰の上限を設定してこそ、運転時エラーに陥ることはありません.
    import sys
sys.setrecursionlimit(100000)
    正しいコード:
    import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
ans = 0

def dfs(x, y):
    graph[x][y] = 0
    dy = [-1, 1, 0, 0, -1, -1, 1, 1]
    dx = [0, 0, -1, 1, -1, 1, -1, 1]
    for i in range(len(dy)):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= N or ny < 0 or ny >= M:
            continue
        if graph[nx][ny]:
            dfs(nx, ny)

for i in range(N):
    for j in range(M):
        if graph[i][j]:
            dfs(i, j)
            ans += 1
print(ans)

    華麗な攻撃を受けた採点結果.
    なぜDFSが解放されたのか、BFSはだめなのかを探ってみましょう.
    「excelのエクスポート」圧力テストの同時多発性によるマルチスレッド競合の問題
    アルゴリズム(Python)