Optimizing Knight Moves Using Dijkstra and Bitmask Dynamic Programming
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need to maximize the minimum score of moves for a knight on a chessboard, starting f
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need to maximize the minimum score of moves for a knight on a chessboard, starting from a given position and visiting a set of positions. We use dynamic programming with bit masking to solve this problem.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nPrecompute Distances:\nUse Dijkstra\'s algorithm to compute the minimum number of moves between every pair of positions. Store these distances in a dpDis table.\n\nDynamic Programming Setup:\nUse a DP table dp[j][bit][turn] where j represents the current position, bit represents the visited positions (encoded as a bitmask), and turn indicates whether we are maximizing or minimizing the score.\n\nRecurrence Relation:\n\nIf all positions are visited (bit has all bits set), return 0.\nDepending on the turn (turn), either maximize or minimize the score by iterating over unvisited positions and computing the score using precomputed distances and recursive results.\nReturn Result:\nStart from the initial position and compute the result using the DP table.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->O(n2\u22C52^n\u22C5log(N^2))\n\n- Space complexity: O(n.2^n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\nint N=51;\nint INF=INT_MAX;\nvector<pair<int, int>> knight_moves = {\n    {-2, -1}, {-2, 1}, {2, -1}, {2, 1},\n    {-1, -2}, {-1, 2}, {1, -2}, {1, 2}\n};\n\nint to_index(int x, int y) {\n    return x * N + y;\n}\n\nbool is_valid(int x, int y) {\n    return (x >= 0 && x < N && y >= 0 && y < N);\n}\nint dijkstra(int i,int j,vector<vector<int>>&pos) {\n    if(dpDis[i][j]!=-1)return dpDis[i][j];\n    int sx=pos[i][0], sy=pos[i][1], dx=pos[j][0], dy=pos[j][1];\n    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n    vector<int> dist(N * N, INF);\n    int start = to_index(sx, sy);\n    dist[start] = 0;\n    pq.push({0, start});\n    \n    while (!pq.empty()) {\n        int current_dist = pq.top().first;\n        int node = pq.top().second;\n        pq.pop();\n        \n        int x = node / N;\n        int y = node % N;\n        \n        if (x == dx && y == dy) {\n         dpDis[i][j]=current_dist;\n         dpDis[j][i]=current_dist;\n            return current_dist;\n        }\n        \n        for (auto move : knight_moves) {\n            int nx = x + move.first;\n            int ny = y + move.second;\n            \n            if (is_valid(nx, ny)) {\n                int next_node = to_index(nx, ny);\n                int new_dist = current_dist + 1;\n                \n                if (new_dist < dist[next_node]) {\n                    dist[next_node] = new_dist;\n                    pq.push({new_dist, next_node});\n                }\n            }\n        }\n    }\n    \n    return -1;\n}\nint dpDis[16][16];\nint dp[16][66000][2];\nint helper(int j,vector<vector<int>>&pos,int bit,int turn ){\n    int ans=0;\n    int x=pos[j][0],y=pos[j][1];\n    if(dp[j][bit][turn]!=-1)return  dp[j][bit][turn];\n    bit=bit|(1<<j);\n    if(turn ==0){\n        for(int i=0;i<pos.size();i++){\n            if(((bit>>i)&1)==0){\n                int newbit=bit|(1<<i);;\n            ans=max(ans,dijkstra(i,j,pos)+helper(i,pos,newbit,!turn));\n           \n            }\n        }\n    }\n    else {\n        ans=INT_MAX;\n          for(int i=0;i<pos.size();i++){\n            if(((bit>>i)&1)==0){\n                int newbit=bit|(1<<i);;\n\n            ans=min(ans,dijkstra(i,j,pos)+helper(i,pos,newbit,!turn));\n          \n            }\n        }\n        if(ans==INT_MAX)ans=0;\n\n    }\n    return dp[j][bit][turn]=ans;\n\n}\n    int maxMoves(int kx, int ky, vector<vector<int>>& pos) {\n        memset(dpDis,-1,sizeof(dpDis));\n        memset(dp,-1,sizeof(dp));\n        int bit=0;\n        // vector<int>vis(n);\n        pos.push_back({kx,ky});\n        int n=pos.size();\n        return helper(n-1,pos,bit,0);\n        \n    }\n};\n```
['Dynamic Programming', 'Graph', 'Shortest Path', 'Bitmask', 'C++']