Problem:


問題文

お菓子の魔女 CHARLOTTE は巴マミとクッキーゲームを楽しんでいる．クッキーゲームは 8\times 8 の格子状に区切られたテーブルクロスの上にチーズクッキーとチョコレートクッキーを置いて行われる．各格子には高々 1 個のチョコレートクッキーまたはチーズクッキーしか置くことはできない．

お菓子の魔女はチーズクッキーを，巴マミはチョコレートクッキーを交互に置いてゲームを行う．自分のクッキーを置いたあと，そのクッキーから上下左右斜めの各 8 方向について，置くクッキーとすでに置いていた自分のクッキーの間に相手のクッキーのみが直線に並んでいた場合に，その挟まれた相手のクッキーのすべてが自分のクッキーで置き換えられる．クッキーゲームのプレイヤーは自分のターンが回ってきた時，1 つ自分のクッキーを置くことができる．ただし，相手のクッキーを少なくとも 1 つ以上自分のクッキーに置き換えられなければならない．そのような置き場がない場合，自分のターンをパスをしなければならない．

お菓子の魔女も巴マミも考えるのが少々苦手である．そこで，回ってきたターン毎にそのターンの中で置き換えられるクッキーの数を最大化することを考えることにした．巴マミのターンのときに置き換えられるクッキーの数を最大にするようなクッキーを置く場所の候補が複数ある場合は，より上の場所を，それでも複数ある場合はより左の場所を選択することにした．また同様に，お菓子の魔女のターンのときに候補が複数ある場合はより下の場所を，それでも複数ある場合はより右の場所を選択することにした．

テーブルクロスに置かれたクッキーの状態が与えられるので，巴マミからはじめ，彼女たちがそこからクッキーゲームを行い，共に新たなクッキーが置けなくなるまでゲームを続けた時のテーブルクロスの上に置かれたクッキーの状態を求めよ．

入力形式

入力は以下の形式で与えられる．

s_{11} s_{12} ... s_{18}\\
s_{21} s_{22} ... s_{28}\\
...\\
s_{81} s_{82} ... s_{88}\\

s_{ij} はテーブルクロスに置かれたクッキーの初期状態を表す文字で，上から i 行目，左から j 列目の格子の状態を表す．チョコレートクッキーが置かれているときs_{ij}は 'o' であり，チーズクッキーが置かれているときは 'x', 何も置かれていないときは '.' となる．

出力形式

クッキーゲームが行われた後のテーブルクロスの上に置かれたクッキーの状態を，入力形式と同じ形式で出力せよ．

制約

s_{ij} は 'o', 'x', '.' のいずれかである．

入出力例

入力例 1

ooox....
.x......
ooo.....
........
........
........
........
........

出力例1

ooooo...
.o......
ooo.....
...o....
....o...
........
........
........

入力例 2

........
........
........
...ox...
...xo...
........
........
........

出力例 2

xxxxxxxx
xxxooxxx
xxxxooxx
xxxxxxxx
ooxxooox
ooxoooox
oxooooox
ooooooox

入力例 3

........
........
..ooo...
..oxo...
..ooo...
........
........
........

出力例 3

........
........
..ooo...
..ooo...
..ooo...
.....o..
......o.
........

Problem Setter: Flat35

Sample input:
ooox....
.x......
ooo.....
........
........
........
........
........


Sample output:
ooooo...
.o......
ooo.....
...o....
....o...
........
........
........

Submission status: Wrong Answer

Solution code:
def search(c,a,b):
    r={'o':'x','x':'o'}
    ans=0
    direct=((-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1))
    for d in range(8):
        y,x=a,b
        i,j=direct[d]
        while s[y+i][x+j]==r[c]:
            y+=i
            x+=j
        if s[y+i][x+j]==c:
            ans+=max(abs(y-a),abs(x-b))

    return ans

def mami():
    m=0
    a=b=-1
    for i in range(1,9):
        for j in range(1,9):
            if s[i][j]=='.':
                t=search('o',i,j)
                if t>m:
                    m=t
                    a,b=i,j
    return(a,b)

def char():
    m=1
    a=b=-1
    for i in range(1,9):
        for j in range(1,9):
            if s[i][j]=='.':
                t=search('x',i,j)
                if t>=m:
                    m=t
                    a,b=i,j
    return(a,b)

def rev(c,a,b):
    #s[a][b]=c
    r={'o':'x','x':'o'}
    direct=((-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1))
    for d in range(8):
        y,x=a,b
        i,j=direct[d]
        while s[y+i][x+j]==r[c]:
            y+=i
            x+=j
        if s[y+i][x+j]==c:
            #i,j=direct[d]
            y,x=a+i,b+j
            while s[y][x]==r[c]:
                s[y][x]=c
                y+=i
                x+=j
    s[a][b]=c

s=[['.']*10]
for _ in range(8):
    s.append(['.']+list(input())+['.'])
s=tuple(s+[['.']*10])

while 1:
    a,b=mami()
    if a>0:
        rev('o',a,b)
    c,d=char()
    if c>0:
        rev('x',c,d)
    if all(i==-1for i in(a,b,c,d)):
        break
for t in s:
    print(*t[1:9],sep='')

Submission status: Wrong Answer

Solution code:
def search(c,a,b):
    r={'o':'x','x':'o'}
    ans=0
    direct=((-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1))
    for d in range(8):
        y,x=a,b
        i,j=direct[d]
        while s[y+i][x+j]==r[c]:
            y+=i
            x+=j
        if s[y+i][x+j]==c:
            ans+=max(abs(y-a),abs(x-b))

    return ans

def mami():
    m=0
    a=b=-1
    for i in range(1,9):
        for j in range(1,9):
            if s[i][j]=='.':
                t=search('o',i,j)
                if t>m:
                    m=t
                    a,b=i,j
    return(a,b)

def char():
    m=1
    a=b=-1
    for i in range(1,9):
        for j in range(1,9):
            if s[i][j]=='.':
                t=search('x',i,j)
                if t>=m:
                    m=t
                    a,b=i,j
    return(a,b)

def rev(c,a,b):
    #s[a][b]=c
    r={'o':'x','x':'o'}
    direct=((-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1))
    for d in range(8):
        y,x=a,b
        i,j=direct[d]
        while s[y+i][x+j]==r[c]:
            y+=i
            x+=j
        if s[y+i][x+j]==c:
            #i,j=direct[d]
            y,x=a+i,b+j
            while s[y][x]==r[c]:
                s[y][x]=c
                y+=i
                x+=j
    s[a][b]=c

s=[['.']*10]
for _ in range(8):
    s.append(['.']+list(input())+['.'])
s=tuple(s+[['.']*10])

while 1:
    a,b=mami()
    if a>0:
        rev('o',a,b)
    c,d=char()
    if c>0:
        rev('x',c,d)
    if all(i==-1for i in(a,b,c,d)):
        break
for t in s[:-1]:
    print(*t[1:9],sep='')

Submission status: Wrong Answer

Solution code:
dxy = zip([1,1,0,-1,-1,-1,0,1],[0,1,1,1,0,-1,-1,-1])

A = [list(raw_input()) for i in xrange(8)]
for i in xrange(64):
    hand = ["o","x"][i%2]
    d = 1-2*(i%2)
    px = py = -1
    mx = 0
    for y in range(8)[::d]:
        for x in range(8)[::d]:
            if A[y][x] == ".":
                for dx,dy in dxy:
                    nx,ny = x+dx,y+dy
                    while 0 <= min(nx,ny) and max(nx,ny) < 8:
                        if   A[ny][nx] == hand:
                            if max(abs(nx-x),abs(ny-y))-1 > mx:
                                mx = max(abs(nx-x),abs(ny-y))-1
                                px,py,dxx,dyy = x,y,dx,dy
                            else:
                                break
                        elif A[ny][nx] == ".":
                            break
                        nx += dx; ny += dy
    if px == py == -1: continue
    while 0 <= min(px,py) and max(px,py) < 8:
        if A[py][px] == hand: break
        A[py][px] = hand
        px += dxx; py += dyy
for a in A:
    print "".join(a)

Submission status: Accepted

Solution code:
mp = [list("X" * 10)] + [list("X" + input() + "X") for _ in range(8)] + [list("X" * 10)]
vec = ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1))
#mami...o, witch...x

def search(target, another, x, y, dx, dy):
  nx, ny = x + dx, y + dy
  cnt = 0
  while mp[ny][nx] == another:
    nx += dx
    ny += dy
    cnt += 1

  if mp[ny][nx] == target:
    return cnt
  else:
    return 0

def score(target, another, x, y):
  ret = 0
  for dx, dy in vec:
    ret += search(target, another, x, y, dx, dy)
  return ret

def locate(target, another, x, y):
  mp[y][x] = target
  for dx, dy in vec:
    if search(target, another, x, y, dx, dy):
      nx, ny = x + dx, y + dy
      while mp[ny][nx] == another:
        mp[ny][nx] = target
        nx += dx
        ny += dy

def temp(target, another, flag):
  max_score = 0
  max_x, max_y = 100, 100
  loop = range(1, 9) if flag else range(8, 0, -1)
  for y in loop:
    for x in loop:
      if mp[y][x] != ".":continue
      new_score = score(target, another, x, y)
      if new_score > max_score:
        max_score = new_score
        max_x, max_y = x, y
  
  if max_score != 0:
    locate(target, another, max_x, max_y)
    return True
  return False

def mami():
  return temp("o", "x", True)

def witch():
  return temp("x", "o", False)

def play():
  while True:
    flag = False
    flag = mami() or flag
    flag = witch() or flag
    if not flag:break
play()
[print("".join(lst[1:-1])) for lst in mp[1:-1]]

Submission status: Accepted

Solution code:
def search(c,a,b):
    r={'o':'x','x':'o'}
    ans=0
    direct=((-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1))
    for d in range(8):
        y,x=a,b
        i,j=direct[d]
        while s[y+i][x+j]==r[c]:
            y+=i
            x+=j
        if s[y+i][x+j]==c:
            ans+=max(abs(y-a),abs(x-b))

    return ans

def mami():
    m=0
    a=b=-1
    for i in range(1,9):
        for j in range(1,9):
            if s[i][j]=='.':
                t=search('o',i,j)
                if t>m:
                    m=t
                    a,b=i,j
    return(a,b)

def char():
    m=1
    a=b=-1
    for i in range(1,9):
        for j in range(1,9):
            if s[i][j]=='.':
                t=search('x',i,j)
                if t>=m:
                    m=t
                    a,b=i,j
    return(a,b)

def rev(c,a,b):
    #s[a][b]=c
    r={'o':'x','x':'o'}
    direct=((-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1))
    for d in range(8):
        y,x=a,b
        i,j=direct[d]
        while s[y+i][x+j]==r[c]:
            y+=i
            x+=j
        if s[y+i][x+j]==c:
            #i,j=direct[d]
            y,x=a+i,b+j
            while s[y][x]==r[c]:
                s[y][x]=c
                y+=i
                x+=j
    s[a][b]=c

s=[['.']*10]
for _ in range(8):
    s.append(['.']+list(input())+['.'])
s=tuple(s+[['.']*10])

while 1:
    a,b=mami()
    if a>0:
        rev('o',a,b)
    c,d=char()
    if c>0:
        rev('x',c,d)
    if all(i==-1for i in(a,b,c,d)):
        break
for t in s[1:-1]:
    print(*t[1:9],sep='')

Submission status: Accepted

Solution code:
from __future__ import print_function
import copy
import sys

class Board(object):
    size = 8
    dy = [0, -1, -1, -1, 0, 1, 1, 1]
    dx = [1, 1, 0, -1, -1, -1, 0, 1]

    def __init__(self):
        self.board = [[0] * Board.size for _ in xrange(Board.size)]

    def __deepcopy__(self, memo):
        ret = Board()
        ret.board = copy.deepcopy(self.board, memo)
        return ret

    def _check_range(self, y, x):
        assert 0 <= y < Board.size and 0 <= x < Board.size

    def _check_color(self, color):
        assert color == 'o' or color == 'x'

    def _putone(self, color, y, x):
        self._check_color(color)
        self._check_range(y, x)

        if color == 'o':
            self.board[y][x] = 1
        if color == 'x':
            self.board[y][x] = -1

    def _getone(self, y, x):
        self._check_range(y, x)
        
        if self.board[y][x] == 1:
            return 'o'
        if self.board[y][x] == -1:
            return 'x'
        return '.'

    def view(self):
        return '\n'.join(''.join(self._getone(y, x) for x in xrange(Board.size)) for y in xrange(Board.size))

    def put(self, color, y, x):
        self._check_color(color)
        self._check_range(y, x)
        self._putone(color, y, x)


        def find(y, x, d):
            # print("y = ", y, ", x = ", x, ", d = ", d)
            if y < 0 or y >= Board.size or x < 0 or x >= Board.size:
                return False
            if self._getone(y, x) == '.':
                return False
            if self._getone(y, x) == color:
                return True
            if find(y + Board.dy[d], x + Board.dx[d], d):
                self._putone(color, y, x)
                return True
            return False

        for d in xrange(Board.size):
            # print('d = ', d)
            find(y + Board.dy[d], x + Board.dx[d], d)
            # print(self.view())

def main():
    board = Board()
    for i in xrange(8):
        l = raw_input()
        for j in xrange(8):
            if l[j] != '.':
                board._putone(l[j], i, j)
    color = 'o'
    passprev = False
    while True:
        cy = -1
        cx = -1
        get = 1
        o = sum(1 for c in board.view() if c == 'o')
        x = sum(1 for c in board.view() if c == 'x')
        if color == 'o':
            for i in xrange(8):
                for j in xrange(8):
                    if board._getone(i, j) == '.':
                        board2 = copy.deepcopy(board)
                        board2.put(color, i, j)
                        o2 = sum(1 for c in board2.view() if c == 'o')
                        if o2 - o > get:
                            get = o2 - o
                            cy = i
                            cx = j
        else:
            for _i in xrange(8):
                for _j in xrange(8):
                    i = 7 - _i
                    j = 7 - _j
                    if board._getone(i, j) == '.':
                        board2 = copy.deepcopy(board)
                        board2.put(color, i, j)
                        x2 = sum(1 for c in board2.view() if c == 'x')
                        if x2 - x > get:
                            get = x2 - x
                            cy = i
                            cx = j

        if cy == -1 and cx == -1:
            if passprev:
                break
            passprev = True
        else:
            passprev = False
            board.put(color, cy, cx)

        if color == 'o':
            color = 'x'
        else:
            color = 'o'

    print(board.view())

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
dxy = zip([1,1,0,-1,-1,-1,0,1],[0,1,1,1,0,-1,-1,-1])
A = [list(raw_input()) for i in xrange(8)]
for i in xrange(64):
    hand = ["o","x"][i%2]
    d = [1,-1][i%2]
    mx,nd = 0,[]
    for y in range(8)[::d]:
        for x in range(8)[::d]:
            if A[y][x] == ".":
                tmp,td = 0,[]
                for dx,dy in dxy:
                    nx,ny = x+dx,y+dy
                    while 0 <= min(nx,ny) and max(nx,ny) < 8:
                        if   A[ny][nx] == hand:
                            get = max(abs(nx-x),abs(ny-y))-1
                            if get > 0:
                                tmp += get
                                td.append([dx,dy])
                            break
                        elif A[ny][nx] == ".":
                            break
                        nx += dx; ny += dy
                if tmp > mx:
                    mx,nd = tmp,td
                    px,py = x,y
    if mx == 0: continue
    A[py][px] = hand
    for dx,dy in nd:
        nx,ny = px+dx,py+dy
        while 0 <= min(nx,ny) and max(nx,ny) < 8:
            if A[ny][nx] == hand: break
            A[ny][nx] = hand
            nx += dx; ny += dy
for a in A:
    print "".join(a)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    dd = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

    while True:
        b = [[c for c in S()] for _ in range(8)]
        def g(ps,i,j,di,dj):
            if not (0 <= i < 8) or not (0 <= j < 8):
                return
            if b[i][j] == '.':
                return
            if b[i][j] == ps:
                return 0
            tr = g(ps,i+di,j+dj,di,dj)
            if tr is None:
                return
            return tr + 1

        def ff(ps,i,j,di,dj):
            if not (0 <= i < 8) or not (0 <= j < 8):
                return
            if b[i][j] == '.':
                return
            if b[i][j] == ps:
                return 0
            tr = ff(ps,i+di,j+dj,di,dj)
            if tr is None:
                return
            b[i][j] = ps
            return tr + 1

        def f(pf, pp):
            ps = 'o'
            es = 'x'
            if not pf:
                ps = 'x'
                es = 'o'
            mc = 0
            mij = (0,0)
            for i in range(8):
                for j in range(8):
                    if b[i][j] != '.':
                        continue
                    c = 0
                    for di,dj in dd:
                        tc = g(ps,i+di,j+dj,di,dj)
                        if not tc is None:
                            c += tc
                    if mc < c or (mc == c and not pf):
                        mc = c
                        mij = (i,j)

            if mc > 0:
                i,j = mij
                b[i][j] = ps
                for di,dj in dd:
                    ff(ps,i+di,j+dj,di,dj)
                f(not pf, False)
            elif pp:
                return
            else:
                f(not pf, True)

        f(True, False)

        for i in range(8):
            rr.append(''.join(b[i]))
        break

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime,time


MAP = [list('z' + input() + 'z') for _ in range(8)]
MAP = [list('z'*10)] + MAP + [list('z'*10)]

def check(x0,y0,turn):
    if MAP[y0][x0] != '.':
        return 0, []

    if turn:
        me,you = 'o','x'
    else:
        me,you = 'x','o'

    ans = 0
    dx = [-1, 0, 1,-1, 1,-1, 0, 1]
    dy = [-1,-1,-1, 0, 0, 1, 1, 1]
    rev = []
    for i in range(8):
        x,y = x0,y0
        cnt = 0
        tmprev = []
        while True:
            x += dx[i]
            y += dy[i]
            if MAP[y][x] == you:
                tmprev.append([x,y])
                cnt += 1
                continue
            elif MAP[y][x] == me:
                break
            else:
                cnt = 0
                tmprev = []
                break
        ans += cnt
        rev = tmprev + rev
    return ans,rev

btmp = -1
turn = True
while True:
    maxtmp = 0
    maxrev = []
    my = []
    ra = list(range(1,9))
    if not turn:
        ra = list(reversed(ra))

    #print(turn,ra)
    for y in ra:
        for x in ra:
            #print(turn,x,y)
            tmp,rev = check(x,y,turn)
            if maxtmp < tmp:
                maxtmp = tmp
                maxrev = rev[:]
                my = [x,y]

    if my:
        if turn:
            MAP[my[1]][my[0]] = 'o'
        else:
            MAP[my[1]][my[0]] = 'x'

    for x,y in maxrev:
        if MAP[y][x] == 'o':
            MAP[y][x] = 'x'
        else:
            MAP[y][x] = 'o'

    #print(maxtmp,my,rev)

    #for m in MAP:
    #    print(''.join(m))

    if btmp == 0 and maxtmp == 0:
        break

    btmp = maxtmp
    turn = not turn

for y in range(1,9):
    print(''.join(MAP[y][1:9]))