Submission #1123063

---

Source Code Expand

import sys
import time
import random
from collections import deque

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = 50
    start = time.time()
    # input
    diag = []
    for i in range(N):
        diag.append(list(input()))

    # process
    numdot, dot = dot_get(N, diag)
    kai3(N, diag, numdot, dot, start)

    # debug output

    # output
    for i in range(N):
        print(''.join(diag[i]))
    
def dot_get(N, diag):
    numdot = 0
    dot = []

    for i in range(N):
        for j in range(N):
            if diag[i][j] == '.':
                dot.append((i, j))
                numdot += 1

    return numdot, dot

def kai3(N, diag, numdot, dot, start):
    score = calc_score(N, diag)
    flag = True

    while 1:
        if flag:
            loop = range(numdot - 1, -1, -1)
        else:
            loop = list(range(numdot))
            random.shuffle(loop)
            
        flag = False
        for k in loop:
            i, j = dot[k]
            if diag[i][j] == '.':
                diag[i][j] = '+'
                score1 = calc_score(N, diag)
                if score1 > score:
                    flag = True
                    score = score1
                    continue
                else:
                    diag[i][j] = '-'
                    score1 = calc_score(N, diag)
                    if score1 > score:
                        flag = True
                        score = score1
                        continue
                    else:
                        diag[i][j] = '.'
            elif diag[i][j] == '+':
                diag[i][j] = '.'
                score1 = calc_score(N, diag)
                if score1 > score:
                    flag = True
                    score = score1
                    continue
                else:
                    diag[i][j] = '-'
                    score1 = calc_score(N, diag)
                    if score1 > score:
                        flag = True
                        score = score1
                        continue
                    else:
                        diag[i][j] = '+'
            elif diag[i][j] == '-':
                diag[i][j] = '.'
                score1 = calc_score(N, diag)
                if score1 > score:
                    flag = True
                    score = score1
                    continue
                else:
                    diag[i][j] = '+'
                    score1 = calc_score(N, diag)
                    if score1 > score:
                        flag = True
                        score = score1
                        continue
                    else:
                        diag[i][j] = '-'

            if time.time() - start > 9.7:
                return None


def kai2(N, diag, numdot, dot, start):
    score = calc_score(N, diag)

    while 1:
        for i in range(N-1, 0, -1):
            for j in range(N-1, -1, -1):
                if diag[i][j] == '.':
                    diag[i][j] = '+'
                    score1 = calc_score(N, diag)
                    if score1 > score:
                        score = score1
                        continue
                    else:
                        diag[i][j] = '-'
                        score1 = calc_score(N, diag)
                        if score1 > score:
                            score = score1
                            continue
                        else:
                            diag[i][j] = '.'
                elif diag[i][j] == '+':
                    diag[i][j] = '.'
                    score1 = calc_score(N, diag)
                    if score1 > score:
                        score = score1
                        continue
                    else:
                        diag[i][j] = '-'
                        score1 = calc_score(N, diag)
                        if score1 > score:
                            score = score1
                            continue
                        else:
                            diag[i][j] = '+'
                elif diag[i][j] == '-':
                    diag[i][j] = '.'
                    score1 = calc_score(N, diag)
                    if score1 > score:
                        score = score1
                        continue
                    else:
                        diag[i][j] = '+'
                        score1 = calc_score(N, diag)
                        if score1 > score:
                            score = score1
                            continue
                        else:
                            diag[i][j] = '-'

                if time.time() - start > 9.7:
                    return None

def kai1(N, diag, start):
    score = calc_score(N, diag)
    for i in range(N-1, -1, -1):
        for j in range(N-1, -1, -1):
            if diag[i][j] == '.':
                diag[i][j] = '+'
                score1 = calc_score(N, diag)
                if score1 > score:
                    score = score1
                    continue
                else:
                    diag[i][j] = '-'
                    score1 = calc_score(N, diag)
                    if score1 > score:
                        score = score1
                        continue
                    else:
                        diag[i][j] = '.'

            if time.time() - start > 9.5:
                return None

    return None

def n_tobasi(N, diag, step, start):
    score = calc_score(N, diag)
    j = 0

    while 1:
        for i in range(N - 1, 0, -1):
            if diag[i][j] == '.':
                diag[i][j] = '+'
                new_score = calc_score(N, diag)
                if new_score > score:
                    score = new_score
                    j = (j + step) % N
                    break

                diag[i][j] = '-'
                new_score = calc_score(N, diag)
                if new_score > score:
                    score = new_score
                    j = (j + step) % N
                    break
                else:
                    diag[i][j] = '.'
        else:
            j = (j + step) % N

        if time.time() - start > 9.5:
            return None


def calc_score(N, diag):
    ''' 消す処理をする前の盤面から点数を計算する '''

    max_o, max_x = 0, 0
    v_diag = vanish_blocks(N, diag)
    checked = [[False]*N for i in range(N)]

    for i in range(N):
        for j in range(N):
            if not checked[i][j] and v_diag[i][j] == 'o':
                max_o = max(max_o, bfs(N, v_diag, checked, i, j, 'o'))
            elif not checked[i][j] and v_diag[i][j] == 'x':
                max_x = max(max_x, bfs(N, v_diag, checked, i, j, 'x'))

    return max_o + max_x

def bfs(N, diag, checked, i, j, sym):
    nxt = deque([(i, j)])
    checked[i][j] = True
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    len_adj = 0

    while nxt:
        x, y = nxt.popleft()
        len_adj += 1

        for k in range(4):
            if 0 <= x + dx[k] < N and 0 <= y + dy[k] < N:
                if not checked[x+dx[k]][y+dy[k]] and diag[x+dx[k]][y+dy[k]] == sym:
                    nxt.append((x+dx[k], y+dy[k]))
                    checked[x+dx[k]][y+dy[k]] = True

    return len_adj


def vanish_blocks(N, diag):
    res = [[' ']*N for i in range(N)]
    for j in range(N):
        pos = N - 1
        for i in range(N - 1, -1, -1):
            if diag[i][j] == '.':
                continue
            elif diag[i][j] == 'o' or diag[i][j] == 'x' or diag[i][j] == '+':
                res[pos][j] = diag[i][j]
                pos -= 1
            elif diag[i][j] == '-':
                res[i][j] = '-'
                pos = i - 1

    return res

if __name__ == '__main__':
    solve()

Submission Info

Judge Result