109 ms | DP + bitmask | pre-caculated BFS | 73 lines after rustfmt
Intuition\n Describe your first thoughts on how to solve this problem. \n\n- dynamic programming\n- move(cur_pos, avail_pos, choose_min) = {max|min} [ dist(cur_
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n- dynamic programming\n- `move(cur_pos, avail_pos, choose_min) = {max|min} [ dist(cur_pos, next_pos) + move(next_pos, avail_pos - next_pos, !choose_min) for next_pos in avail_pos]`: alice choose the maximum and bob choose the minimum.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSome optimization method:\n- Since there are at most 16 postions (including knight), a 16 bits integer can be used to indicate available postions/taken postions.\n- whether choose_min is true can be known from parity of the count of visited positions\n- minimum moves between any two positons can be cached / pre-caculated.\n\n# Complexity\n- Time complexity: $$O(n * 2 ^ n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n * 2 ^ n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```rust []\nimpl Solution {\n\tpub fn max_moves(kx: i32, ky: i32, positions: Vec<Vec<i32>>) -> i32 {\n\t\tlet mut pos = vec![[kx, ky]];\n\t\tpos.extend(positions.iter().map(|v| [v[0], v[1]]));\n\t\tSelf::solve(\n\t\t\t0,\n\t\t\t&pos,\n\t\t\t1,\n\t\t\t&mut vec![vec![[-1, -1]; pos.len()]; 1 << pos.len()],\n\t\t\t&mut Self::dists(&pos),\n\t\t)\n\t}\n\tfn solve(\n\t\tsi: usize,\n\t\tpos: &[[i32; 2]],\n\t\tvis: u16,\n\t\tstate: &mut [Vec<[i32; 2]>],\n\t\tdist: &mut [Vec<i32>],\n\t) -> i32 {\n\t\tlet min = vis.count_ones() % 2 == 0; // true for Bob, false for Alice\n\t\tif state[vis as usize][si][min as usize] != -1 {\n\t\t\treturn state[vis as usize][si][min as usize];\n\t\t} else if vis.trailing_ones() == pos.len() as u32 {\n\t\t\treturn 0;\n\t\t}\n\t\tlet it = (0..pos.len())\n\t\t\t.filter(|&pi| (1 << pi) & vis == 0)\n\t\t\t.map(|pi| dist[si][pi] + Self::solve(pi, pos, vis | (1 << pi), state, dist));\n\t\tlet ans = if min { it.min() } else { it.max() }.unwrap();\n\t\tstate[vis as usize][si][min as usize] = ans;\n\t\tans\n\t}\n\tfn dists(pos: &[[i32; 2]]) -> Vec<Vec<i32>> {\n\t\tlet mut dist = vec![vec![9999; pos.len()]; pos.len()];\n\t\tfor (i, &s) in (0..).zip(pos) {\n\t\t\tlet mut dis = [[9999; 50]; 50];\n\t\t\tlet mut dq = vec![s];\n\t\t\tdis[s[0] as usize][s[1] as usize] = 0;\n\t\t\tlet mut dep = 0;\n\t\t\twhile !dq.is_empty()\n\t\t\t\t&& pos\n\t\t\t\t\t.iter()\n\t\t\t\t\t.any(|p| dis[p[0] as usize][p[1] as usize] == 9999)\n\t\t\t{\n\t\t\t\tdep += 1;\n\t\t\t\tfor [x, y] in std::mem::take(&mut dq) {\n\t\t\t\t\tfor [nx, ny] in [\n\t\t\t\t\t\t[x + 1, y + 2],\n\t\t\t\t\t\t[x + 1, y - 2],\n\t\t\t\t\t\t[x - 1, y + 2],\n\t\t\t\t\t\t[x - 1, y - 2],\n\t\t\t\t\t\t[x + 2, y + 1],\n\t\t\t\t\t\t[x + 2, y - 1],\n\t\t\t\t\t\t[x - 2, y + 1],\n\t\t\t\t\t\t[x - 2, y - 1],\n\t\t\t\t\t] {\n\t\t\t\t\t\tif (0..50).contains(&nx)\n\t\t\t\t\t\t\t&& (0..50).contains(&ny)\n\t\t\t\t\t\t\t&& dis[nx as usize][ny as usize] > dep\n\t\t\t\t\t\t{\n\t\t\t\t\t\t\tdis[nx as usize][ny as usize] = dep;\n\t\t\t\t\t\t\tdq.push([nx, ny]);\n\t\t\t\t\t\t}\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t\tfor (j, p) in (0..).zip(pos) {\n\t\t\t\tdist[i][j] = dis[p[0] as usize][p[1] as usize];\n\t\t\t}\n\t\t}\n\t\tdist\n\t}\n}\n```
['Rust']