[Python] ABC015 C 幅優先探索

[Python] ABC015 C メモ化再帰

この問題ではメモ化再帰を使う必要はないのですが、前述の問題を、練習のためメモ化再帰を使って解きなおします。 問題 C - 高橋くんのバグ探し 回答 defaultdict defaultdict をメモに使ってみます。 .fo...

yottagin.com

2019-12-12 11:36

幅優先探索で実装します。

問題

C – 高橋くんのバグ探し

回答

N, K = map(int, input().split())
T = [list(map(int, input().split())) for _ in range(N)]

cur_vals = [0]
for n in range(N):
    new_vals = []
    for cur_val in cur_vals:
        for val in T[n]:
            new_val = cur_val ^ val
            new_vals.append(new_val)
    cur_vals = new_vals

if 0 in cur_vals:
    print('Found')
else:
    print('Nothing')