結果
問題 | No.2984 [Cherry Anniversary 4] 満開の願いを込めた 27 の桜 |
ユーザー |
|
提出日時 | 2024-12-07 00:17:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,717 ms / 4,000 ms |
コード長 | 3,252 bytes |
コンパイル時間 | 206 ms |
コンパイル使用メモリ | 82,316 KB |
実行使用メモリ | 88,848 KB |
最終ジャッジ日時 | 2024-12-08 23:31:46 |
合計ジャッジ時間 | 47,652 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
import sys, time, random from collections import deque, Counter, defaultdict def debug(*x):print('debug:',*x, file=sys.stderr) input = lambda: sys.stdin.readline().rstrip() ii = lambda: int(input()) mi = lambda: map(int, input().split()) li = lambda: list(mi()) inf = 2 ** 61 - 1 mod = 998244353 #3*3*3のマス目に対し、行を入れ替える操作繰り返してできるマス目を列挙 S = [[[(i, j, k) for k in range(3)] for j in range(3)] for i in range(3)] def swap1(S, i, j): S = list(list(list(x) for x in y) for y in S) S[i], S[j] = S[j], S[i] return S def swap2(S, i, j): S = list(list(list(x) for x in y) for y in S) for k in range(3): S[k][i], S[k][j] = S[k][j], S[k][i] return S def swap3(S, i, j): S = list(list(list(x) for x in y) for y in S) for k in range(3): for l in range(3): S[k][l][i], S[k][l][j] = S[k][l][j], S[k][l][i] return S allsigma = set() cost = defaultdict(lambda : inf) Q = deque() Q.append(S) cost[tuple(tuple(tuple(x) for x in y) for y in S)] = 0 allsigma.add(tuple(tuple(tuple(x) for x in y) for y in S)) while Q: S = Q.popleft() c = cost[tuple(tuple(tuple(x) for x in y) for y in S)] for i in range(3): for j in range(i+1, 3): T = swap1(tuple(tuple(tuple(x) for x in y) for y in S), i, j) if cost[tuple(tuple(tuple(x) for x in y) for y in T)] > c + 1: cost[tuple(tuple(tuple(x) for x in y) for y in T)] = c + 1 allsigma.add(tuple(tuple(tuple(x) for x in y) for y in T)) Q.append(T) T = swap2(tuple(tuple(tuple(x) for x in y) for y in S), i, j) if cost[tuple(tuple(tuple(x) for x in y) for y in T)] > c + 1: cost[tuple(tuple(tuple(x) for x in y) for y in T)] = c + 1 allsigma.add(tuple(tuple(tuple(x) for x in y) for y in T)) Q.append(T) T = swap3(tuple(tuple(tuple(x) for x in y) for y in S), i, j) if cost[tuple(tuple(tuple(x) for x in y) for y in T)] > c + 1: cost[tuple(tuple(tuple(x) for x in y) for y in T)] = c + 1 allsigma.add(tuple(tuple(tuple(x) for x in y) for y in T)) Q.append(T) def solve(): A = [[li() for _ in range(3)] for _ in range(3)] X = [li() for _ in range(3)] Y = [li() for _ in range(3)] Z = [li() for _ in range(3)] ans = inf for S in allsigma: B = [[[0]*3 for _ in range(3)] for _ in range(3)] for i in range(3): for j in range(3): for k in range(3): B[i][j][k] = A[S[i][j][k][0]][S[i][j][k][1]][S[i][j][k][2]] #X,Y,Zの値を検算 ok = True for i in range(3): for j in range(3): if B[0][i][j] + B[1][i][j] + B[2][i][j] != X[i][j]: ok = False if B[i][0][j] + B[i][1][j] + B[i][2][j] != Y[i][j]: ok = False if B[i][j][0] + B[i][j][1] + B[i][j][2] != Z[i][j]: ok = False if ok: ans = min(ans, cost[tuple(tuple(tuple(x) for x in y) for y in S)]) print(ans if ans != inf else -1) for _ in range(ii()): solve()