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