1536. 排布二进制网格的最少交换次数

贪心即可

class Solution {
public:
    vector<int> v[410];
    vector<int> record;
    int vis[410];
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size();
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                int k;
                for(k = i + 1; k < n; k++)
                {
                    if(grid[j][k] != 0) break;
                }
                if(k == n) v[i].push_back(j);
            }
        }



        int ret = 0;
        for(int i = 0; i < n - 1; i++)
        {
            if(v[i].size() == 0) return -1;
            int len = v[i].size();
            int flag = 0;
            for(int j = 0; j < len; j++)
            {
                int y = v[i][j];
                if(vis[y] == 0)
                {
                    flag = 1;
                    vis[y] = 1;
                    // cout << y << "  ";
                    record.push_back(y);
                    int y1 = y;
                    for(int k = 0; k < record.size(); k++)
                    {
                        if(y < record[k])
                        {
                            y1 += 1;
                        }
                    }
       
                    // cout << y << "  ";
                    // cout << i << "   " << y - i << "  " << endl;
                    ret += y1 - i;
                    break;

                }
            }
            if(flag == 0) return -1;
        }
        return ret;





    }
};

 

上一篇:hdu 7136 Jumping Monkey (并查集,重构树)


下一篇:最短路(搬运)