レベルアップ問題集Python3 エンタメSTEINS;GATE問題セット

<正則表現のエントリーポイント>
# 正則表現のエントリーポイント D
# utf-8
a = input()
b = input()

ans = a + ";" + b
print(ans)
'''
改行で区切られた 2 つの単語の入力を受け取ります。
受け取った 2 つの単語を 単語 1、単語 2 とすると、
単語 1 と ; と 単語 2 をこの順で連結させます。
'''

<性能解析タイプセーフ>
# 性能解析タイプセーフ C
# utf-8
v = input().split()
N = int(v[0])
K = float(v[1])

total = 0
for _ in range(N):
    x = float(input())
    total += round(x * 10)

ans = int(total / round(K * 10))
if total % round(K * 10) != 0:
    ans += 1
print(ans)
'''
 解答の流れ・考え方 】
途中で 10 倍したり、直感的でない式が出てきたりしますが、後ほど説明します。
まず、N と K を受け取ります。
i=1 から i=N までの round(x_i*10) の合計値を求めます。round() は引数の数値を丸める関数だと考えてください。
解は次の式で求められる整数部分です。
(合計 + round(K*10)-1) / round(K*10)
整数部分を出力することに注意してください。
【 10 倍する理由 】
コンピュータ内部では小数を完全に表現することができません。
そのため、小数演算を繰り返すことで、誤差が発生することが多々あります。
そこで、今回入力される小数の条件は小数点以下 1 桁の小数だということに注目して、小数を 10 倍することで、小数演算を回避します。
【 丸める理由 】
先述の通り、コンピュータ内部では小数を完全に表現することができません。
そのため、単に 10 倍するだけでは、誤差が残ることがあります。
そこで、丸めをおこない、その誤差に対応した整数を生成します。
【 解を求める式について 】
合計 / round(K*10) の整数部分を出力すると不正解になることがあります。
この節では、問題点と解決策について説明します。
【 ここで使う記号について 】
X: 整数の被除数(割られる数)
Y: 整数の除数(割る数)
A: X / Y の整数部分
C: X / Y の余り
【 問題点 】
これは、合計 / round(K*10) の小数部分を無視していることに起因します (式の答えが 1.1 のとき、経験値は 2 必要)
【 解決策 】
小数点以下を切り上げることができれば解決できます。
方法を以下にいくつか示します。
if 文を使う
ceiling 関数を使う
X に Y - 1 を足す
3. で小数点以下の切り上げが実現できる理由を以下で説明します。
まず、Y = 3 のとき、表にすると以下のようになります。
X	2	3	4	5	6
X / Y の整数部	0	1	1	1	2
X + Y-1	4	5	6	7	8
(X + Y-1) / Y の整数部	1	1	2	2	2
この表から切り上げが成功しているように見えますが、以下で少し数学的に確認します。
いま、以下の式が成立しています。
X = A * Y + C
両辺に Y - 1 を足します。
X + Y - 1 = A * Y + C + Y - 1
この式は C の値によって以下のように整理できます。(以下の式に出てくる D は式を整理したあとにでてくる新たな余りを意味します)
C = 0 のとき: X + Y - 1 = A * Y + D
C ≠ 0 のとき: X + Y - 1 = (A + 1) * Y + D
(C ≠ 0 のとき、1 ≦ C ≦ Y-1 であるから、Y ≦ C + Y - 1 ≦ 2(Y - 1) であり、C + Y - 1 は Y でくくることができる)
上記の D を余りとした式を Y で割ったときの商は、
C = 0 のとき: A
C ≠ 0 のとき: A + 1
となるので、小数点以下の切り上げができることが確認できました。
'''

<例外処理のタブーサーチ>
step1 整数値の差 D
# utf-8
a, b = map(int, input().split())
print(b - a)

step2 数列の差 D
# utf-8
n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

for i in range(n):
    if i < n - 1:
        print(b[i] - a[i], end=" ")
    else:
        print(b[i] - a[i])
'''
for ループなどを用いて、数列の各要素の差 b_i-a_i を計算しながら出力すればよいです。
'''

step3 整数値の検索 C
# utf-8
n = int(input())
a = [int(x) for x in input().split()]
x = int(input())

pos_of_x = -1
for i in range(n):
    if a[i] == x:
        pos_of_x = i + 1
        break

print(pos_of_x)
'''
for ループなどで数列の要素を 1 つずつ取り出し、 x と等しいかどうかを確かめればよいです。
'''

step4 数列の検索 C
# utf-8
m, n = map(int, input().split())
a = []
for i in range(m):
    a.append([int(t) for t in input().split()])
x = [int(t) for t in input().split()]

pos_of_x = -1
for i in range(m):
    is_x = True
    for j in range(n):
        if a[i][j] != x[j]:
            is_x = False

    if is_x:
        pos_of_x = i + 1
        break

print(pos_of_x)
'''
与えられた m 個の各数列について、X と等しいかどうかを確かめればよいです。
'''

final 例外処理のタブーサーチ B
# utf-8
n, m, l = map(int, input().split())
d = [[int(x) for x in input().split()] for i in range(n)]
p = [[int(x) for x in input().split()] for i in range(l)]

for i in range(1, l):
    diff = [p[i][j] - p[i - 1][j] for j in range(m)]

    order = -1
    for j in range(n):
        same = True
        for k in range(m):
            if diff[k] != d[j][k]:
                same = False
        if same:
            order = j + 1
            break

    print(order)
'''
各時刻 i について時刻 i -> i+1 のパラメータ変化量を計算し、該当するコマンドを探索します。
'''

<進化戦略のプロシージャ>
step1 ダンジョンのデッドロック1 C
# utf-8
n, m, q = map(int, input().split())
s = [int(input()) for _ in range(m)]

s.insert(0, -1)
for _ in range(q):
    e, t = map(int, input().split())
    if s[e] == t:
        print("Yes")
        continue

    for i in range(1, m + 1):
        if i != e and s[i] == t:
            print("No")
            break

        if i == m:
            print("Yes")
'''
それぞれ E_i 番目のプレイヤー (1 ≦ i ≦ Q) について、部屋を移動できるかの判定を以下のようにします。
S_{E_i} == T_i なら、部屋を移動しないので "Yes" を出力します。
S_j == T_i を満たす j (1 ≦ j ≦ M, j ≠ E_i) が存在するなら、部屋を移動できないので "No" を出力します。
上のどれにも当てはまらないなら、部屋を移動できるので "Yes" を出力します。

'''

step2 ダンジョンのデッドロック2 C
# utf-8
n, m, q = map(int, input().split())

room = [-1] * (n + 1)
for i in range(m):
    s = int(input())
    room[s] = i + 1 # room[i] には i 番目の部屋にいるプレイヤーの番号が格納されています。

for _ in range(q):
    e, t = map(int, input().split())
    if room[t] == -1 or room[t] == e:
        print("Yes")
    else:
        print("No")
'''
前問の解説で紹介したプログラムでは、各質問に対して N 人のプレイヤーを見ていたため、全体の計算量は O(NQ) になり、この問題の制約では制限時間に間に合いません。
それぞれ E_i 番目のプレイヤー (1 ≦ i ≦ Q) について、部屋を移動できるかの判定を以下のようにします。
部屋が空いているかどうかを配列 room[] で管理します。
room[x] が true なら部屋 x が埋まっていて、false なら部屋が空いています。
S_{E_i} == T_i であるか、room[T_i] == false であるなら、部屋を移動できるので "Yes" を出力します。そうでないなら、部屋を移動できないので "No" を出力します。
このようにすることで、各質問に対して数回の計算で答えを求めることができ、全体の計算量は O(N+Q) となり制限時間に間に合います。
'''

step3 ダンジョンのデッドロック3 B
# utf-8
n, m = map(int, input().split())

room = [-1] * (n + 1) # room[i] には i 番目の部屋にいるプレイヤーの番号が格納されています。
req = [-1] * (m + 1) # req[k] には k 番目のプレイヤーの移動先が格納されています。
for i in range(m):
    s, t = map(int, input().split())
    room[s] = i + 1
    req[i + 1] = t

q = [1]
while True:
    p = q[-1]

    if room[req[p]] == -1:
        break
    if room[req[p]] == p:
        break

    q.append(room[req[p]])

print(" ".join(map(str, reversed(q))))
'''
答えを表す配列 players を用意し、部屋の移動をするプレイヤーを変数 P で保存します。P の初期値は 1 とします。
移動先の部屋が空くまで、players に P を追加し、P に "移動先の部屋に滞在しているプレイヤー" を代入することを繰り返します。
部屋を移動できるかの判定や、移動先の部屋に滞在しているプレイヤーの番号の取得は、以下のようにします。
それぞれの席に滞在しているプレイヤーの番号を配列 room[] で管理します。
room[T_P] で、移動先の部屋に滞在しているプレイヤーの番号が得られます。
room[T_P] == 0 で、移動先の部屋にプレイヤーが滞在していないことを判定できます。
移動先のプレイヤーから順に部屋の移動をするため、players は逆順で出力します。
'''

step4 ダンジョンのデッドロック4 B
# utf-8
n, m = map(int, input().split())

room = [-1] * (n + 1)
req = [-1] * (m + 1)
for i in range(m):
    s, t = map(int, input().split())
    room[s] = i + 1
    req[i + 1] = t

ans = False
q = [1]
while True:
    p = q[-1]

    if room[req[p]] == -1:
        break
    if room[req[p]] == p:
        break
    if room[req[p]] == 1:
        ans = True
        break

    q.append(room[req[p]])

if ans:
    print("Yes")
else:
    print("No")
    print(" ".join(map(str, reversed(q))))
'''
問題文の条件 S_i ≠ S_j, T_i ≠ T_j (i ≠ j) から、次のことが言えます。
入力を (S_i, T_i) (1 ≦ i ≦ M) を辺とする、頂点が N 個で、 辺が M 本のグラフとしてみたとき、
デッドロックが発生していない ⇔ 頂点 1 を含む連結成分が直線型のグラフ (パス) になっている
デッドロックが発生している ⇔ 頂点 1 を含む連結成分が円形のグラフ (ループ) になっている
つまり, 1 番目のプレイヤーから始めて部屋の移動先にいるプレイヤーをたどっていったときに、1 番目のプレイヤーの元の部屋に戻ってきてしまうかどうかでデッドロックの発生を判定できます。
答えを表す配列 players を用意し、部屋の移動をするプレイヤーを変数 P で保存します。P の初期値は 1 とします。
デッドロックが発生するか、部屋を移動できることが確定するまで、players に P を追加し、P に "移動先の部屋に滞在しているプレイヤー" を代入することを繰り返します。
デッドロックの発生の判定、部屋を移動できるかの判定や、移動先の部屋に滞在しているプレイヤーの番号の取得は、以下のようにします。
それぞれの部屋に滞在しているプレイヤーの番号を配列 room[] で管理します。
room[T_P] で、移動先の部屋に滞在しているプレイヤーの番号が得られます。
room[T_P] == 0 で、移動先の部屋にプレイヤーが滞在していないことを判定できます。
room[T_P] == 1 で、1 番目のプレイヤーの元の部屋に戻ってきてしまったことを判定できます。特に P ≠ 1 のとき、これはデッドロックを表します。
移動先の部屋のプレイヤーから順に部屋の移動をするため、players は逆順で出力します。
'''

step5 ダンジョンのデッドロック5 A
# utf-8
n, m = map(int, input().split())

room = [-1] * (n + 1)
req = [-1] * (m + 1)
for i in range(m):
    s, t = map(int, input().split())
    room[s] = i + 1
    req[i + 1] = t

ans = False
for i in range(1, m + 1):
    p = i
    while True:
        if room[req[p]] == -1:
            break
        if room[req[p]] == p:
            break
        if room[req[p]] == i:
            ans = True
            break

        p = room[req[p]]

if ans:
    print("Yes")
else:
    print("No")
'''
問題文の条件 S_i ≠ S_j, T_i ≠ T_j (i ≠ j) から、次のことが言えます。
入力を (S_i, T_i) (1 ≦ i ≦ M) を辺とする、頂点が N 個で、辺が M 本のグラフとしてみたとき、
　連結成分でデッドロックが発生していない ⇔ 連結成分が直線型のグラフ (パス) になっている
　連結成分でデッドロックが発生している ⇔ 連結成分が円形のグラフ (ループ) になっている
つまり, それぞれのプレイヤーから始めて移動先にいるプレイヤーをたどっていったときに、最初のプレイヤーの元の部屋に戻ってきてしまうかどうかでデッドロックの発生を判定できます。
すべてのプレイヤーについて、以下のような探索をおこないます。プレイヤーの代わりに部屋について探索してもかまいません。
選んだプレイヤーから始めて、デッドロックの発生の判定、部屋を移動できるかの判定をしながら、プレイヤーをたどって見ていきます。
'''

final 進化戦略のプロシージャ A
# utf-8
n, m = map(int, input().split())

room = [-1] * (n + 1)
req = [-1] * (m + 1)
for i in range(m):
    s, t = map(int, input().split())
    room[s] = i + 1
    req[i + 1] = t

ans = False
visit = [False] * (m + 1)
for i in range(1, m + 1):
    p = i
    while True:
        if visit[p]:
            break

        visit[p] = True

        if room[req[p]] == -1:
            break
        if room[req[p]] == p:
            break
        if room[req[p]] == i:
            ans = True
            break

        p = room[req[p]]

if ans:
    print("Yes")
else:
    print("No")
'''
問題文の条件 S_i ≠ S_j, T_i ≠ T_j (i ≠ j) から、次のことが言えます。
入力を (S_i, T_i) (1 ≦ i ≦ M) を辺とする、頂点が N 個で、辺が M 本のグラフとしてみたとき、
連結成分でデッドロックが発生していない ⇔ 連結成分が直線型のグラフ (パス) になっている
連結成分でデッドロックが発生している ⇔ 連結成分が円形のグラフ (ループ) になっている
つまり, それぞれのから始めて移動先にいるプレイヤーをたどっていったときに、最初のプレイヤーに戻ってきてしまうかどうかでデッドロックの発生を判定できます。
すべてのプレイヤーについて、以下のような探索をおこないます。プレイヤーの代わりに部屋について探索してもかまいません。
選んだプレイヤーから始めて、デッドロックの発生の判定、部屋を移動できるかの判定をしながら、プレイヤーをたどって見ていきます。
すでにプレイヤーが探索済みのときに探索をしないことで、全体での探索の回数がプレイヤーの数を超えることがなくなり、制限時間に間に合います。
'''

<ネット・ガーディアンの奮闘>
step1 最大連結成分(4×4) A
# utf-8
import queue

di = [-1, 1, 0, 0]
dj = [0, 0, 1, -1]

g = [[int(x) for x in input().split()] for _ in range(4)]

max_score = 0
max_bit = 0

for bit in range(1, 2 ** 16):
    choice = [[False for _ in range(4)] for _ in range(4)]
    cell_num = 0
    score = 0
    for k in range(16):
        if ((bit >> k) & 1) == 1:
            cell_num += 1
            si, sj = divmod(k, 4)
            choice[si][sj] = True
            score += g[si][sj]
    if score < max_score:
        continue

    q = queue.Queue()
    choice[si][sj] = False
    q.put([si, sj])
    while not q.empty():
        i, j = q.get()
        cell_num -= 1
        for k in range(4):
            ni, nj = i + di[k], j + dj[k]
            if ni in range(4) and nj in range(4) and choice[ni][nj] == True:
                choice[ni][nj] = False
                q.put([ni, nj])

    if cell_num == 0:
        max_bit = bit
        max_score = score

for i in range(4):
    for j in range(4):
        print(max_bit >> (i * 4 + j) & 1, end="")
    print()
'''
再帰やビット全探索を用いて、集合の選び方を全探索します。
各集合に対して、連結かどうかを判定し、連結であれば暫定解の更新をおこないます。
'''

step2 塊を作ろう A
# utf-8
import queue

di = [-1, 1, 0, 0]
dj = [0, 0, 1, -1]

h, w = map(int, input().split())
g = [[int(x) for x in input().split()] for _ in range(h)]

visit = [[False for _ in range(w)] for _ in range(h)]

answer = 0
for i in range(h):
    for j in range(w):
        if g[i][j] < 0 or visit[i][j]:
            continue

        answer += 1

        q = queue.Queue()
        visit[i][j] = True
        q.put([i, j])
        while not q.empty():
            pi, pj = q.get()
            for k in range(4):
                ni, nj = pi + di[k], pj + dj[k]
                if (
                    ni in range(h)
                    and nj in range(w)
                    and not visit[ni][nj]
                    and g[ni][nj] >= 0
                ):
                    visit[ni][nj] = True
                    q.put([ni, nj])

print(answer)
'''
幅優先探索や深さ優先探索を用いて、0 以上の整数が書かれたセルのみからなる連結成分の数を数えます。
'''

step3 セルとセルを繋ごう A
# utf-8
import queue

di = [-1, 1, 0, 0]
dj = [0, 0, 1, -1]

h, w = map(int, input().split())
si, sj, gi, gj = map(lambda x: int(x) - 1, input().split())
g = [[-int(x) for x in input().split()] for _ in range(h)]

dist = [[2 ** 30 for _ in range(w)] for _ in range(h)]
dist[si][sj] = g[si][sj]

pq = queue.PriorityQueue()
pq.put((g[si][sj], si, sj))

while not pq.empty():
    d, i, j = pq.get()

    if dist[i][j] != d:
        continue

    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if ni in range(h) and nj in range(w) and d + g[ni][nj] < dist[ni][nj]:
            dist[ni][nj] = d + g[ni][nj]
            pq.put((dist[ni][nj], ni, nj))

print(-dist[gi][gj])
'''
セルに書かれた整数を正負反転させると、グリッドグラフ上の最短経路問題として解くことができるようになります。
距離の初期値として、非常に大きな値 2^30 を設定しています。
優先度つきキュー queue.PriorityQueue を用いて、ダイクストラ法によって最短経路問題を解いています。
'''

step4 塊と塊を繋ごう A
# utf-8
import queue

di = [-1, 1, 0, 0]  # 上下左右の移動量のリスト
dj = [0, 0, 1, -1]

h, w = map(int, input().split())
g = [[0 if (int(x) > 0) else -int(x) for x in input().split()] for _ in range(h)]  # グリッドの値を変換

dist = [[2 ** 30 for _ in range(w)] for _ in range(h)]  # 最短距離を保持する2次元リスト
dist[0][0] = 0  # セル(1, 1)からの最短距離を0と設定

pq = queue.PriorityQueue()  # 優先度付きキューを作成
pq.put((dist[0][0], 0, 0))  # セル(1, 1)を追加

while not pq.empty():
    d, i, j = pq.get()  # 最短距離が最小の要素を取り出す

    if dist[i][j] != d:  # 取り出した要素の最短距離が既に更新されている場合はスキップ
        continue

    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if ni in range(h) and nj in range(w) and d + g[ni][nj] < dist[ni][nj]:  # 最短距離を更新できる場合
            dist[ni][nj] = d + g[ni][nj]  # 新たな最短距離を計算し、更新
            pq.put((dist[ni][nj], ni, nj))  # 更新されたセルをキューに追加

print(-dist[h - 1][w - 1])  # セル(H, W)までの最短距離の絶対値を出力
'''
優先度付きキューを使用してDijkstraのアルゴリズムを実装しています。

まず、グリッドの値を変換し、正連結成分に含まれるセルの値を0に、正連結成分に含まれないセルの値を正負逆に設定しています。これにより、セルの値を足し合わせることでスコアを計算できるようになります。

次に、最短距離を保持する2次元配列distを初期化し、セル(1, 1)からの最短距離を0として設定します。

優先度付きキューpqには、セルの最短距離と座標をタプルとして追加します。初期状態では、セル(1, 1)が追加されます。

pqが空になるまで以下の処理を繰り返します。

pqから最短距離が最小の要素を取り出します。
取り出した要素の最短距離がdistに保存されている最短距離と一致しない場合は、スキップします。これにより、既に更新されたセルの重複を防ぎます。
セルの上下左右の隣接セルに対して、最短距離を更新できる場合は、新たな最短距離を計算し、distとpqに追加します。
最後に、distからセル(H, W)までの最短距離を取り出し、その絶対値を求めて出力します。これが連結成分のスコアになります。
'''

step5 ネット・ガーディアンの奮闘(易) A
# utf-8
import queue

di = [-1, 1, 0, 0]
dj = [0, 0, 1, -1]

h, w = map(int, input().split())
g = [[int(x) for x in input().split()] for _ in range(h)]

group = [[0 for _ in range(w)] for _ in range(h)]
group_num = 1
max_group_num = -1
max_score = 0

for i in range(h):
    for j in range(w):
        if group[i][j] != 0 or g[i][j] < 0:
            continue

        q = queue.Queue()
        group[i][j] = group_num
        q.put([i, j])
        score = g[i][j]

        while not q.empty():
            pi, pj = q.get()
            for k in range(4):
                ni, nj = pi + di[k], pj + dj[k]
                if (
                    ni in range(h)
                    and nj in range(w)
                    and group[ni][nj] == 0
                    and g[ni][nj] >= 0
                ):
                    group[ni][nj] = group_num
                    score += g[ni][nj]
                    q.put([ni, nj])

        if score > max_score:
            max_group_num = group_num
            max_score = score

        group_num += 1

for i in range(h):
    for j in range(w):
        if group[i][j] == max_group_num:
            print(1, end="")
        else:
            print(0, end="")
    print()
'''
前問までの内容を踏まえて、なるべくスコアが大きくなるように工夫してセルを選びましょう。
正誤判定に用いるスコアが低く設定されているため、例えば 0 以上の値が書かれたセルのみを選択したときにできる連結成分のスコアの最大値 以上のスコアを持つ連結成分を出力すれば、正解することができます。
'''

final ネット・ガーディアンの奮闘 A
# utf-8
'''
この解答例の方針は以下の通りです。
0 以上の値を持つセルを選択したときにできる連結成分を用意する
負の値を持つセルについてのみ値の正負を反転させたグリッドグラフ上で、各連結成分 A から他の連結成分への最短経路問題を解く
最短で到達できる連結成分 B について、セルの集合 (A + B + 最短経路に含まれるセル) を求める
3 で求めた集合のうち、スコア最大のものを出力する
この解答例で出力される集合はグリッド全体に対して非常に小さいものとなっており、改善の余地がまだまだあります。
'''
import queue

di = [-1, 1, 0, 0]
dj = [0, 0, 1, -1]

h, w = map(int, input().split())
g = [[int(x) for x in input().split()] for _ in range(h)]

group = [[0 for _ in range(w)] for _ in range(h)]
group_num = 1
group_score = [-1]

for i in range(h):
    for j in range(w):
        if group[i][j] != 0 or g[i][j] < 0:
            continue

        q = queue.Queue()
        group[i][j] = group_num
        q.put([i, j])
        score = g[i][j]

        while not q.empty():
            pi, pj = q.get()
            for k in range(4):
                ni, nj = pi + di[k], pj + dj[k]
                if (
                    ni in range(h)
                    and nj in range(w)
                    and group[ni][nj] == 0
                    and g[ni][nj] >= 0
                ):
                    group[ni][nj] = group_num
                    score += g[ni][nj]
                    q.put([ni, nj])

        group_score.append(score)
        group_num += 1

# 連結成分が 1 つだった場合はそれをそのまま出力
if group_num == 2:
    for i in range(h):
        for j in range(w):
            print(group[i][j], end="")
        print()
    exit(0)

# 暫定解のスコア
max_score = -1000000

group_done = set()
for i in range(h):
    for j in range(w):
        if group[i][j] == 0 or group[i][j] in group_done:
            continue

        group_done.add(group[i][j])

        dist = [[2 ** 30 for _ in range(w)] for _ in range(h)]
        dist[i][j] = 0

        prev = [[None for _ in range(w)] for _ in range(h)]

        bef = (i, j)
        now = (i, j)
        si, sj = now

        pq = queue.PriorityQueue()
        pq.put((dist[i][j], bef, now))

        while not pq.empty():
            d, bef, now = pq.get()
            si, sj = now

            if dist[si][sj] != d:
                continue

            prev[si][sj] = bef

            if group[si][sj] != 0 and group[si][sj] != group[i][j]:
                break

            for k in range(4):
                ni = si + di[k]
                nj = sj + dj[k]

                if ni not in range(h) or nj not in range(w):
                    continue

                ndist = d - min(0, g[ni][nj])

                if ndist < dist[ni][nj]:
                    dist[ni][nj] = ndist
                    pq.put((dist[ni][nj], now, (ni, nj)))

        score = group_score[group[i][j]] - dist[si][sj] + group_score[group[si][sj]]

        if score <= max_score:
            continue

        # つなぐ 2 つの連結成分
        group1, group2 = group[i][j], group[now[0]][now[1]]
        # 暫定解の更新
        max_score = score
        # 最短路の復元
        shortest_path = [[False for _ in range(w)] for _ in range(h)]
        while prev[now[0]][now[1]] != now:
            now = prev[now[0]][now[1]]
            shortest_path[now[0]][now[1]] = True

# 答えを出力
for i in range(h):
    for j in range(w):
        if shortest_path[i][j] or group[i][j] in [group1, group2]:
            print(1, end="")
        else:
            print(0, end="")
    print()