Python | Bitmask DP | BFS
Complexity\n- Time complexity:\nO(n2^n)\n\n- Space complexity:\nO(n2^n)\n\n# Code\npython3 []\nclass Solution:\n    \n\n    def maxMoves(self, kx: int, ky: int,
# Complexity\n- Time complexity:\n$$O(n*2^n)$$\n\n- Space complexity:\n$$O(n*2^n)$$\n\n# Code\n```python3 []\nclass Solution:\n    \n\n    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:\n        moves = [(2,1),(1,2)]\n        cases = [(1,1),(1,-1),(-1,1),(-1,-1)]\n\n        min_dis = defaultdict(int)\n        d = defaultdict(int)\n        n = len(positions)+1\n        positions.append([kx,ky])\n        for i in range(n):\n            d[(positions[i][0],positions[i][1])] = i + 1\n        for i,j in d:\n            q = deque()\n            q.append((i,j))\n            s = set()\n            taken = 1<<(d[(i,j)]-1)\n            cnt = 0\n            while q:\n                qq = len(q)\n                for _ in range(qq):\n                    x,y = q.popleft()\n                    if (x,y) in d:\n                        min_dis[(x,y,i,j)] = cnt\n                        min_dis[(i,j,x,y)] = cnt \n                        taken |= 1<<(d[(i,j)]-1)\n                    s.add((x,y))\n                    for xx,yy in moves:\n                        for xxx,yyy in cases:\n                            if 0<=x-xx*xxx<50 and 0<=y-yy*yyy<50 and (x-xx*xxx,y-yy*yyy) not in s:\n                                s.add((x-xx*xxx,y-yy*yyy))\n                                q.append((x-xx*xxx,y-yy*yyy))\n                cnt += 1\n                if taken+1 == 2**n:\n                    break\n\n        dp = {}\n        def f(kx,ky,taken,turn):\n            if 1<<n == taken+1:\n                return 0\n            if (kx,ky,taken) in dp:\n                return dp[(kx,ky,taken)]\n\n            ans = float("-inf")\n            if not turn:\n                ans = float("inf")\n            \n            for i in range(n):\n                if taken&1<<i:\n                    continue\n                if turn:\n                    ans = max(ans,min_dis[(kx,ky,positions[i][0],positions[i][1])]+f(positions[i][0],positions[i][1],taken|1<<i,1-turn))\n                else:\n                    ans =  min(ans,min_dis[(kx,ky,positions[i][0],positions[i][1])]+f(positions[i][0],positions[i][1],taken|1<<i,1-turn))\n\n            dp[(kx,ky,taken)] = ans\n            return ans\n        return f(kx,ky,1<<(n-1),1)\n                                    \n\n\n\n\n\n\n            \n\n\n\n```
['Python3']