hdu 5386 Cover（暴力求解+想法題）

題意：

有兩種操作：
操作L x y，把當前x，這一列全部置為y
操作H x y，把當前，這一行全部置為y。
現在給你n∗n的初始矩陣，以及n∗n的目標矩陣
現在給你m種操作（由以上兩種操作構成），問怎麼排序這m種操作，才能使得，初始矩陣，經由排序後的操作，構成目標矩陣。
輸出排序方案。

解析：

逆向思維，
枚舉每個操作，然後判斷該操作是不是最後一個操作。（就像撕膠布一樣，一條一條的剝離）
判斷是否是最後一個操作方法就是：
除去已經用過的點，如果一排都等於當前操作的顏色，那就是最後一個操作。然後再把操作過的點給標記，重復m次。
最後逆向輸出記錄下的id。

my code

#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int M = 505;
const int N = 105;
int tar[N][N];
struct Oper {
    int x, color, id;
    Oper() {}
    Oper(int x, int color, int id) : x(x), color(color), id(id) {}
} H[M], L[M];

int nh, nl, n, m;
int order[M];

bool visH[M], visL[M];

int check(int x, int color, char type) {
    if(type == 'H') {
        for(int i = 1; i <= n; i++) {
            if(tar[x][i] == INF) continue;
            if(tar[x][i] != color)
                return false;
        }
    }else {
        for(int i = 1; i <= n; i++) {
            if(tar[i][x] == INF) continue;
            if(tar[i][x] != color)
                return false;
        }
    }
    return true;
}

void setColor(int x, char type) {
    if(type == 'H') {
        for(int i = 1; i <= n; i++)
            tar[x][i] = INF;    
    }else {
        for(int i = 1; i <= n; i++)
            tar[i][x] = INF;
    }
}

void solve() {
    int cnt = 0;
    while(cnt < m) {
        for(int i = 0; i < nh; i++) {
            if(visH[i]) continue;
            if(check(H[i].x, H[i].color, 'H')) {
                setColor(H[i].x, 'H');
                visH[i] = true;
                order[cnt++] = H[i].id;
            }
        }
        for(int i = 0; i < nl; i++) {
            if(visL[i]) continue;
            if(check(L[i].x, L[i].color, 'L')) {
                setColor(L[i].x, 'L');
                visL[i] = true;
                order[cnt++] = L[i].id;
            }
        }
    }
}

int main() {
    int T;
    scanf(%d, &T);
    while(T--) {
        scanf(%d%d, &n, &m);

        int tmp;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                scanf(%d, &tmp);

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                scanf(%d, &tar[i][j]);

        memset(visH, false, sizeof(visH));
        memset(visL, false, sizeof(visL));
        nh = nl = 0;

        char oper[5];
        int x, color;
        for(int i = 1; i <= m; i++) {
            scanf(%s%d%d, oper, &x, &color);
            if(oper[0] == 'H') H[nh++] = Oper(x, color, i);
            else L[nl++] = Oper(x, color, i);
        }

        solve();
        printf(%d, order[m-1]);
        for(int i = m-2; i >= 0; i--)
            printf( %d, order[i]);
        puts();
    }
    return 0;
}