TCCC 2003 Round 4 Level1

ChessMetric.py

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class ChessMetric:
    def howMany(self, size, start, end, numMoves):
        dx = [1, 1, 1, 0, -1, -1, -1, 0, 2, 1, -1, -2, -2, -1, 1, 2]
        dy = [1, 0, -1, -1, -1, 0, 1, 1, -1, -2, -2, -1, 1, 2, 2, 1]
        dp = [[[0 for i in range(55)] for j in range(100)] for k in range(100)]

        dp[start[0]][start[1]][0] = 1

        for i in range(1, numMoves + 1):
            for x in range(size):
                for y in range(size):
                    for j in range(16):
                        nx = x + dx[j]
                        ny = y + dy[j]
                        if nx >= 0 and ny >= 0 and nx < size and ny < size:
                            dp[nx][ny][i] += dp[x][y][i - 1]

        return dp[end[0]][end[1]][numMoves]