Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.3 kB
2
Indexable
Never
    int minmoves = INT_MAX;
    int solution(vector<vector<int>>& A) 
    {
        vector<pair<int,int>> empty;
        vector<pair<int,int>> nonempty; // excluding cells with 1
        int n = A.size();
        for(int i=0; i< n; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                if (A[i][j] == 0) empty.push_back({i,j});
                else if (A[i][j] > 1) nonempty.push_back({i,j});
            }
        }
        findmoves(empty, nonempty, 0, 0, A);
        return minmoves;
    }
    void findmoves(vector<pair<int,int>> &empty, vector<pair<int,int>> &nonempty, int index, int mov, vector<vector<int>>& A)
    {
        int m = nonempty.size();
        int n = empty.size();
        if(index == n)
        {
            minmoves = min(minmoves, mov);
            return;
        }
        auto& pr1 = empty[index];
        for(int i = 0; i < m; i++)
        {
            auto& pr2 = nonempty[i];
            if(A[pr2.first][pr2.second] > 1)
            {
                int diff = abs(pr2.first - pr1.first) + abs(pr2.second - pr1.second);
                A[pr2.first][pr2.second]--;
                findmoves(empty, nonempty, index + 1, mov + diff, A);
                A[pr2.first][pr2.second]++;
            }
        }
    }
Leave a Comment