Iterative Bit DP (pull based)
Intuition\n Describe your first thoughts on how to solve this problem. \nSame as the other solutions.\n\n# Approach\n Describe your approach to solving the prob
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSame as the other solutions.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIterative bit DP.\n\n# Complexity\n- Time complexity:\n$$O(2^N * N^2 + N^2HW)$$\n\n- Space complexity:\n$$O(2^N * N + N^2)$$\n\n# Code\n```java []\nclass Solution {\n    final int[] dx = new int[] { -2, -1, 1, 2, -2, -1, 1, 2 };\n    final int[] dy = new int[] { -1, -2, -2, -1, 1, 2, 2, 1 };\n    final int h = 50;\n    final int w = 50;\n\n    int bfs(int sx, int sy, int gx, int gy) {\n        final Deque<Integer> que = new ArrayDeque();\n        final int[][] d = new int[h][w];\n        for (int i = 0; i < h; i++) {\n            for (int j = 0; j < w; j++) {\n                d[i][j] = -1;\n            }\n        }\n        que.addLast((sx << 7) | sy);\n        d[sx][sy] = 0;\n        while (!que.isEmpty()) {\n            int cur = que.pollFirst();\n            int x = (cur >> 7) & ((1 << 7) - 1);\n            int y = cur & ((1 << 7) - 1);\n            if (x == gx && y == gy)\n                return d[x][y];\n            for (int i = 0; i < 8; i++) {\n                int nx = x + dx[i];\n                int ny = y + dy[i];\n                if (nx < 0 || ny < 0 || nx >= w || ny >= h)\n                    continue;\n                if (d[nx][ny] != -1)\n                    continue;\n                d[nx][ny] = d[x][y] + 1;\n                que.addLast((nx << 7) | ny);\n            }\n        }\n        return -1;\n    }\n\n    public int maxMoves(int kx, int ky, int[][] positions) {\n        final int n = positions.length;\n        final int[][] dp = new int[1 << n][n];\n        for (int s = 0; s < 1 << n; s++) {\n            Arrays.fill(dp[s], -1);\n        }\n        final int[][] dist = new int[n + 1][n + 1];\n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n                int d = bfs(positions[i][0], positions[i][1], positions[j][0], positions[j][1]);\n                dist[i][j] = d;\n                dist[j][i] = d;\n            }\n        }\n        for (int i = 0; i < n; i++) {\n            final int d = bfs(kx, ky, positions[i][0], positions[i][1]);\n            dist[i][n] = d;\n            dist[n][i] = d;\n        }\n        for (int i = 0; i < n; i++) {\n            dp[1 << i][i] = 0;\n        }\n        for (int s = 0; s < 1 << n; s++) {\n            final int k = n - Integer.bitCount(s);\n            for (int i = 0; i < n; i++) {\n                if (((s >> i) & 1) == 0)\n                    continue;\n                int lastS = s ^ (1 << i);\n                for (int j = 0; j < n; j++) {\n                    if (((lastS >> j) & 1) == 0)\n                        continue;\n                    if (dp[lastS][j] == -1 || dist[i][j] < 0)\n                        continue;\n                    if (k % 2 == 0) {\n                        // bob\'s turn\n                        if (dp[s][i] == -1 || dp[s][i] > dp[lastS][j] + dist[i][j]) {\n                            dp[s][i] = dp[lastS][j] + dist[i][j];\n                        }\n                    } else {\n                        // alice\'s turn\n                        if (dp[s][i] == -1 || dp[s][i] < dp[lastS][j] + dist[i][j]) {\n                            dp[s][i] = dp[lastS][j] + dist[i][j];\n                        }\n                    }\n                }\n            }\n        }\n        int result = 0;\n        for (int i = 0; i < n; i++) {\n            result = Math.max(dist[n][i] + dp[(1 << n) - 1][i], result);\n        }\n        return result;\n    }\n}\n```
['Java']