SRM 447 div1 easy

実装

# coding: utf-8

d = ((-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1))
blocked = [[False for i in range(8)] for j in range(8)]
def calc(y,x):
    if 0 <= y < 8 and 0 <= x < 8 and (not blocked[y][x]):
        ret = 0
        for dy,dx in d:
            ny,nx = dy+y,dx+x
            if 0 <= ny < 8 and 0 <= nx < 8 and (not blocked[ny][nx]):
                ret += 1
        return ret
    return 100

class KnightsTour:
    def visitedPositions(self, board):
        for r,i in zip(board,range(8)):
            for c,j in zip(r,range(8)):
                if c == 'K':
                    y,x = i,j
                elif c == '*':
                    blocked[i][j] = True
        ans = 0
        while True:
            blocked[y][x] = True
            t = None
            s = 9
            for dy,dx in d:
                p = calc(y + dy, x + dx)
                if p < s:
                    s = p
                    t = (y+dy,x+dx)
            if t is not None:
                y,x = t
                ans += 1
            else:
                ans += 1
                break
        return ans