codeforces 816 C. Karen and Game（模拟+思维）

题目链接：http://codeforces.com/contest/816/problem/C

题意：给出一个矩阵，问能否从都是0的情况下只将一整行+1或者一整列+1变形过来，如果可以输出需要步数最小的情况。不能输出-1

题解：就是一道模拟题，然后关于最小的只要考虑一种情况，就是当前行可以消除，也可以消除全部列的时候要考虑要删行还是删列，这个取决于n于m的大小

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int Max_Size = 5e2 + 10;

int a[Max_Size][Max_Size] , Minrow[Max_Size] , Mincol[Max_Size];

struct TnT {

    string pos;

    int num;

}T[Max_Size * Max_Size];

int main() {

    int n , m;

    cin >> n >> m;

    for(int i = 1 ; i <= n ; i++) {

        for(int j = 1 ; j <= m ; j++) {

            cin >> a[i][j];

        }

    }

    memset(Minrow , 0 , sizeof(Minrow));

    memset(Mincol , 0 , sizeof(Mincol));

    for(int i = 1 ; i <= n ; i++) {

        int Min = Max_Size;

        for(int j = 1 ; j <= m ; j++) {

            Min = min(Min , a[i][j]);

        }

        Minrow[i] = Min;

    }

    for(int i = 1 ; i <= m ; i++) {

        int Min = Max_Size;

        for(int j = 1 ; j <= n ; j++) {

            Min = min(Min , a[j][i]);

        }

        Mincol[i] = Min;

    }

    int ans = 0;

    for(int i = 1 ; i <= n ; i++) {

        if(m > n) {

            for(int j = 1 ; j <= m ; j++) {

                a[i][j] -= Minrow[i];

                Mincol[j] = min(Mincol[j] , a[i][j]);

            }

            for(int j = 1 ; j <= Minrow[i] ; j++) {

                T[ans].pos = "row";

                T[ans].num = i;

                ans++;

            }

            Minrow[i] = 0;

        }

    }

    for(int i = 1 ; i <= m ; i++) {

        if(m <= n) {

            for(int j = 1 ; j <= n ; j++) {

                a[j][i] -= Mincol[i];

                Minrow[j] = min(Minrow[j] , a[j][i]);

            }

            for(int j = 1 ; j <= Mincol[i] ; j++) {

                T[ans].pos = "col";

                T[ans].num = i;

                ans++;

            }

            Mincol[i] = 0;

        }

    }

    for(int i = 1 ; i <= n ; i++) {

        for(int j = 1 ; j <= m ; j++) {

            a[i][j] -= Minrow[i];

            Mincol[j] = min(Mincol[j] , a[i][j]);

        }

        for(int j = 1 ; j <= Minrow[i] ; j++) {

            T[ans].pos = "row";

            T[ans].num = i;

            ans++;

        }

        Minrow[i] = 0;

    }

    for(int i = 1 ; i <= m ; i++) {

        for(int j = 1 ; j <= n ; j++) {

            a[j][i] -= Mincol[i];

            Minrow[j] = min(Minrow[j] , a[j][i]);

        }

        for(int j = 1 ; j <= Mincol[i] ; j++) {

            T[ans].pos = "col";

            T[ans].num = i;

            ans++;

        }

        Mincol[i] = 0;

    }

    int flag = 0;

    for(int i = 1 ; i <= n ; i++) {

        for(int j = 1 ; j <= m ; j++) {

            if(a[i][j]) flag = 1;

        }

    }

    if(!flag) {

        cout << ans << endl;

        for(int i = 0 ; i < ans ; i++) cout << T[i].pos << ' ' << T[i].num << endl;

    }

    else cout << -1 << endl;

    return 0;

}

巴特西

codeforces 816 C. Karen and Game（模拟+思维）

最新文章

热门文章