Shortest path+ bit mask dp beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\npair<int,int> fn(int i,int cu,vector<vector<pair<int,int>>> &dp,vector<vector<pair<int,int>>> &g)\n{\n    //cout<<i<<" "<<cu<<endl;\n     if(dp[i][cu].first!=-1)\n     return dp[i][cu];\n   \n     int mi=1e9;\n     int ma=-2;\n     int n=g.size();\n     //cout<<dp[0].size()<<endl;\n       if(cu==dp[0].size()-1)\n       return dp[i][cu]={0,0};\n     for(auto &j: g[i])\n     {\n        int in=j.first,c=j.second;\n        if((1<<in)&cu)\n        continue;\n        \n        auto it=fn(in,(cu|(1<<in)),dp,g);\n        if(it.first==1e9||it.second==-2)\n        continue;\n        ma=max(ma,c+it.first);\n        mi=min(mi,c+it.second);\n     }\n     //cout<<i<<" "<<cu<<" "<<mi<<" "<<ma<<endl;\n     return dp[i][cu]={mi,ma};\n}\nstruct cell {\n    int x, y;\n    int dis;\n    cell() {}\n    cell(int x, int y, int dis)\n        : x(x)\n        , y(y)\n        , dis(dis)\n    {\n    }\n};\n\n// Utility method returns true if (x, y) lies\n// inside Board\nbool isInside(int x, int y, int N)\n{\n    if (x >= 1 && x <= N && y >= 1 && y <= N)\n        return true;\n    return false;\n}\n\n// Method returns minimum step\n// to reach target position\nint minSt(vector<int> knightPos, vector<int> targetPos,\n                         int N)\n{\n    // x and y direction, where a knight can move\n    int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 };\n    int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 };\n\n    // queue for storing states of knight in board\n    queue<cell> q;\n\n    // push starting position of knight with 0 distance\n    q.push(cell(knightPos[0], knightPos[1], 0));\n\n    cell t;\n    int x, y;\n    bool visit[N + 1][N + 1];\n\n    // make all cell unvisited\n    memset(visit, false, sizeof(visit));\n\n    // visit starting state\n    visit[knightPos[0]][knightPos[1]] = true;\n\n    // loop until we have one element in queue\n    while (!q.empty()) {\n        t = q.front();\n        q.pop();\n\n        // if current cell is equal to target cell,\n        // return its distance\n        if (t.x == targetPos[0] && t.y == targetPos[1])\n            return t.dis;\n\n        // loop for all reachable states\n        for (int i = 0; i < 8; i++) {\n            x = t.x + dx[i];\n            y = t.y + dy[i];\n\n            // If reachable state is not yet visited and\n            // inside board, push that state into queue\n            if (isInside(x, y, N) && !visit[x][y]) {\n                visit[x][y] = true;\n                q.push(cell(x, y, t.dis + 1));\n            }\n        }\n    }\n\n    // If no valid path found, return -1\n    return -1;\n}\nclass Solution {\n\npublic:\n    int maxMoves(int kx, int ky, vector<vector<int>>& pos) {\n        pos.push_back({kx,ky});\n        int n=pos.size();\n        vector<vector<pair<int,int>>> g(n);\n        for(auto &i: pos)\n        {\n            i[0]++;\n            i[1]++;\n        }\n        for(int i=0;i<n;i++)\n        {\n             for(int j=i+1;j<n;j++)\n             {\n                 \n                 \n                int x= minSt(pos[i],pos[j],50);\n                if(x!=-1)\n                {\n                    g[i].push_back({j,x});\n                    g[j].push_back({i,x});\n                }\n             }\n        }\n        vector<vector<pair<int,int>>> dp(n,vector<pair<int,int>>((1<<n),{-1,-1}));\n        return fn(n-1,(1<<(n-1)),dp,g).second;\n        \n       \n    \n        \n    }\n};\n```
['Dynamic Programming', 'Shortest Path', 'Bitmask', 'C++']