#2016s ライフゲーム第3世代まで表示

def update(m, N):
    """
    配列mを次世代に更新する関数（問題文の図3を実装）
    m: マスの状態を保持する1次元配列 (1-indexed)
    N: 盤の一辺の大きさ
    """
    # 配列mを配列tempにコピーして退避する[2]
    temp = list(m)
    
    # 配列mの全ての要素の値を0にする[2]
    for i in range(1, N * N + 1):
        m[i] = 0
        
    # iを1からN*Nまで1ずつ増やすループ[2]
    for i in range(1, N * N + 1):
        
        # αの処理：チェックするマスが盤の第1列又は第N列の場合の探索範囲調整[2, 3]
        if (i - 1) % N == 0:
            a = 0
            b = 1
        elif i % N == 0:
            a = -1
            b = 0
        else:
            a = -1
            b = 1
            
        e = 0
        for y in range(-1, 2):
            for x in range(a, b + 1):
                if y != 0 or x != 0:
                    c = i + y * N + x
                    # 計算した位置が盤の外側にはみ出していないかチェック[2, 4]
                    if 1 <= c <= N * N:
                        # [カ] temp[c]と1が等しい (隣接マスが「生」か判定)[2, 5]
                        if temp[c] == 1:
                            e += 1
                            
        # 生死を判定する
        # [キ] 誕生の判定: (temp[i]と0が等しい) and (eと3が等しい)[2, 6]
        if temp[i] == 0 and e == 3:
            m[i] = 1
        # 生存の判定: (temp[i]と1が等しい) and ((eと2が等しい) or (eと3が等しい))[2, 6]
        elif temp[i] == 1 and (e == 2 or e == 3):
            # [ク] m[i] ← 1[2, 3]
            m[i] = 1

def print_board(m, N, generation):
    """
    盤面をN×Nのグリッド形式で視覚的に表示する関数
    """
    print(f"--- 第{generation}世代 ---")
    for row in range(N):
        # 1-indexedに基づき、各行の開始・終了インデックスを計算
        start = row * N + 1
        end = row * N + N + 1
        
        # 値が1(生)なら'○'、0(死)なら'×'として表示（図1の凡例に準拠）[1]
        line = " ".join(["○" if val == 1 else "×" for val in m[start:end]])
        print(line)
    print()

if __name__ == "__main__":
    N = 4  # 4×4マスの盤面[1]
    
    # 配列mの初期化。インデックス0はダミーとして0を入れ、
    # インデックス1〜16に図1の「第1世代」の生死状態をセットする[1]
    m = [0,  # ダミー
         0, 1, 0, 0,  # 1行目: × ○ × ×
         0, 0, 1, 0,  # 2行目: × × ○ ×
         1, 1, 1, 0,  # 3行目: ○ ○ ○ ×
         0, 0, 0, 0]  # 4行目: × × × ×
         
    # 第1世代の表示
    print_board(m, N, 1)
    
    # 第2世代に更新して表示
    update(m, N)
    print_board(m, N, 2)
    
    # 第3世代に更新して表示
    update(m, N)
    print_board(m, N, 3)