题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5386

题意:给你一个n*n的初始矩阵 再给你一个n*n的目标矩阵,然后有两种操作:L X Y表示将第X列全部替换成Y,H X Y表示将第X行全部替换为Y,给你m次操作让你安排顺序使得初始矩阵转换成目标矩阵,输出任意一种可行顺序

解法:题目保证一定有解,又因为操作是整行或整列替换且初始矩阵没有用(会覆盖),所以可以假设为零矩阵,然后从目标矩阵开始通过给的操作使整行或整列变为零,直到目标矩阵变为零矩阵,然后逆序输出操作序号,过程纯暴力。

不太懂这个原理:所以粘贴了一个证明,这道题的贪心是这样的:假设有一个操作op1,最后的它操作后是某行全变成a1颜色,而在最终状态时,的确这行全是a1,那么就可以把这个操作放在最后,因为即使可行的答案不是这样的,经过这样移动操作后,还是能够成为最终状态的,同理,以此向前寻找,但是注意,确定的某个操作后,它操作的那行或列,要全化为0,因为无论前面把它变成什么颜色,最后一步,总会变成这样,符合要求,所以不重要,一般情况先,从后想前推完后,要和初始状态比较一下,但是这道题确定有答案,所以,就可以省掉比较的那个步骤。


#include <bits/stdc++.h>
using namespace std;
int a[105][105], ans[505];
struct node{
    char c[2];
    int x,y;
}op[505];

int main()
{
    int T,n,m;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d %d", &n,&m);
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                scanf("%d", &a[i][j]);
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                scanf("%d", &a[i][j]);
        for(int i=1; i<=m; i++){
            scanf("%s%d%d", op[i].c,&op[i].x,&op[i].y);
        }
        int cnt = 0, j;
        while(cnt < m){
            for(int i=1; i<=m; i++){
                if(!op[i].x) continue;
                int x = op[i].x;
                if(op[i].c[0] == 'L'){
                    for(j=1; j<=n; j++){
                        if(a[j][x]&&a[j][x]!=op[i].y) break;
                    }
                    if(j>n){
                        ans[++cnt]=i,op[i].x=0;
                        for(int j=1; j<=n; j++) a[j][x]=0;
                    }
                }
                else{
                    for(j=1; j<=n; j++){
                        if(a[x][j]&&a[x][j]!=op[i].y) break;
                    }
                    if(j>n){
                        ans[++cnt]=i,op[i].x=0;
                        for(int j=1; j<=n; j++) a[x][j]=0;
                    }
                }
            }
        }
        for(int i=m; i>=1; i--){
            if(i==1) printf("%d\n", ans[i]);
            else printf("%d ", ans[i]);
        }
    }
    return 0;
}