Submission #1531700

---

Source Code Expand

from collections import defaultdict
from itertools import product
from math import pi
import copy

b, c = None, None

def calc(field):
    t, n = 0, 0
    for y in range(3):
        for x in range(3):
            if y + 1 < 3:
                if field[y][x] == field[y + 1][x]:
                    t += b[y][x]
                else:
                    n += b[y][x]
            if x + 1 < 3:
                if field[y][x] == field[y][x + 1]:
                    t += c[y][x]
                else:
                    n += c[y][x]
    return t, n

memo = {}


def lt(l):
    return tuple(l[0]), tuple(l[1]), tuple(l[2])


def dfs(i, field):
    if i >= 9:
        return calc(field)

    if lt(field) in memo:
        return memo[lt(field)]

    mark = i % 2

    t_score, n_score = 0, 0
    for y in range(3):
        for x in range(3):
            if field[y][x] is None:
                f = copy.deepcopy(field)
                f[y][x] = mark
                t, n = dfs(i + 1, f)

                if i % 2 == 0 and t > t_score:
                    t_score, n_score = t, n
                elif i % 2 == 1 and n > n_score:
                    t_score, n_score = t, n

    memo[lt(field)] = t_score, n_score
    return t_score, n_score


def main():
    global b, c
    b1 = list(map(int, input().split()))
    b2 = list(map(int, input().split()))
    b = [b1, b2]
    c1 = list(map(int, input().split()))
    c2 = list(map(int, input().split()))
    c3 = list(map(int, input().split()))
    c = [c1 + [0], c2 + [0], c3 + [0]]

    field = [[None] * 3 for _ in range(3)]
    print(*dfs(0, field), sep="\n")


if __name__ == '__main__':
    main()

Submission Info

Judge Result