2850. Minimum Moves to Spread Stones Over Grid

You are given a 0-indexed 2D integer matrix grid of size 3 * 3, representing the number of stones in each cell. The grid contains exactly 9 stones, and there can be multiple stones in a single cell.

In one move, you can move a single stone from its current cell to any other cell if the two cells share a side.

Return the minimum number of moves required to place one stone in each cell.

c++

class Solution {
    int dp[1<<9];
    int helper(vector<pair<int,int>>& Z, vector<pair<int,int>>& O, int mask, int p) {
        if(p == O.size()) return 0;
        if(dp[mask] != -1) return dp[mask];
        int& res = dp[mask] = 101010;
        for(int i = 0; i < Z.size(); i++) {
            if((mask >> i) & 1) continue;
            int dis = abs(Z[i].first- O[p].first) + abs(Z[i].second - O[p].second);
            res = min(res, dis + helper(Z,O,mask | (1ll<<i), p + 1));
        }
        return res;
    }
public:
    int minimumMoves(vector<vector<int>>& grid) {
        int res = 0;
        memset(dp,-1,sizeof dp);
        vector<pair<int,int>> zero, over;
        for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) {
            if(grid[i][j] == 0) zero.push_back({i,j});
            else if(grid[i][j] > 1) {
                for(int k = 1; k < grid[i][j]; k++) over.push_back({i,j});
            }
        }
        return helper(zero,over,0,0);;
    }
};