HDU——Cover——————【技巧】
2024-10-12 11:38:34
Cover
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1027 Accepted Submission(s): 351
Special Judge
Problem Description
You have an n∗n matrix.Every grid has a color.Now there are two types of operating:
L x y: for(int i=1;i<=n;i++)color[i][x]=y;
H x y:for(int i=1;i<=n;i++)color[x][i]=y;
Now give you the initial matrix and the goal matrix.There are m operatings.Put in order to arrange operatings,so that the initial matrix will be the goal matrix after doing these operatings
L x y: for(int i=1;i<=n;i++)color[i][x]=y;
H x y:for(int i=1;i<=n;i++)color[x][i]=y;
Now give you the initial matrix and the goal matrix.There are m operatings.Put in order to arrange operatings,so that the initial matrix will be the goal matrix after doing these operatings
It's guaranteed that there exists solution.
Input
There are multiple test cases,first line has an integer T
For each case:
First line has two integer n,m
Then n lines,every line has n integers,describe the initial matrix
Then n lines,every line has n integers,describe the goal matrix
Then m lines,every line describe an operating
For each case:
First line has two integer n,m
Then n lines,every line has n integers,describe the initial matrix
Then n lines,every line has n integers,describe the goal matrix
Then m lines,every line describe an operating
1≤color[i][j]≤n
T=5
1≤n≤100
1≤m≤500
Output
For each case,print a line include m integers.The i-th integer x show that the rank of x-th operating is i
Sample Input
1
3 5
2 2 1
2 3 3
2 1 3
3 3 3
3 3 3
3 3 3
H 2 3
L 2 2
H 3 3
H 1 3
L 2 3
Sample Output
5 2 4 3 1
题目大意:给你一个n*n的矩阵,给你初始矩阵和目标矩阵,然后有m个操作。H x z表示将第x行覆盖为z,L x z表示将第x列覆盖为z,保证是有解。问你这m个操作怎么排,可以让初始矩阵变为目标矩阵。
解题思路:遍历m个操作,如果是行操作,就看该行是否都是所要染的颜色或着是0颜色,如果这一行跟要染的颜色一样,那么就存起来操作,同时把该行全部变为0,。由于不是一次下来就能得到结果,所以用一个变量记录已经有多少个操作已经在结果中,最后逆序输出即为答案。
#include<bits/stdc++.h>
using namespace std;
struct Oper{
int r_,x,col;
}opers[550];
int Map[125][125],ans[550],vis[550];
int main(){
int t,a,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);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&Map[i][j]);
}
}
int a,b;
char str[20];
for(int i=1;i<=m;i++){
scanf("%s%d%d",str,&a,&b);
if(str[0]=='H'){
opers[i].r_=1;
opers[i].x=a;
opers[i].col=b;
}else{
opers[i].r_=0;
opers[i].x=a;
opers[i].col=b;
}
}
memset(vis,0,sizeof(vis));
int cnt=0;
while(cnt<m){
for(int i=1;i<=m;i++){
if(!vis[i]){
if(opers[i].r_==1){
int r=opers[i].x,aim=opers[i].col;
int j;
for(j=1;j<=n;j++){
if(Map[r][j]!=aim&&Map[r][j]!=0){
break;
}
}
if(j==n+1){
for(j = 1;j<=n;j++){
Map[r][j]=0;
}
ans[cnt]=i;
cnt++;
vis[i]=1;
}
}else{
int c=opers[i].x,aim=opers[i].col;
int j;
for(j=1;j<=n;j++){
if(Map[j][c]!=aim&&Map[j][c]!=0){
break;
}
}
if(j==n+1){
for(j = 1;j<=n;j++){
Map[j][c]=0;
}
ans[cnt]=i;
cnt++;
vis[i]=1;
}
}
}
}
}
printf("%d",ans[cnt-1]);
for(int i=cnt-2;i>=0;i--){
printf(" %d",ans[i]);
}printf("\n");
}
return 0;
}
最新文章
- console 输出信息
- 十进制数转化成二进制后包含一的数量(c++)
- DOM Element节点类型详解
- NHibernate系列文章四:NHibernate运行时监控
- HTTP协议(待完善)
- Linux 删除mysql数据库失败的解决方法
- Android消息机制之实现两个不同线程之间相互传递数据相互调用
- AIX-du
- Swift继承的用法
- http概览
- Linux网卡配置与绑定
- Asp.Net MVC 之 Autofac 初步使用2 集成mvc 属性注入以及自动注入
- linux vi 报错 E37: No write since last change (add ! to override)
- Swift中集合类型indexOf(Element)提示错误的解决办法
- 跨域iframe如何实现高度自适应?
- python学习之路之int()奇怪的报错
- VMWAR-workstatuon
- 平板电脑安装Ubuntu教程
- 常用模块(json/pickle/shelve/XML)
- hdu 4964 恶心模拟