题目链接: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;
}