首页 > 代码库 > hdu5386 棋盘涂色模拟
hdu5386 棋盘涂色模拟
http://acm.hdu.edu.cn/showproblem.php?pid=5386
Problem Description
You have an 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 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.
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 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
For each case:
First line has two integer ,
Then lines,every line has integers,describe the initial matrix
Then lines,every line has integers,describe the goal matrix
Then lines,every line describe an operating
For each case:
First line has two integer ,
Then lines,every line has integers,describe the initial matrix
Then lines,every line has integers,describe the goal matrix
Then lines,every line describe an operating
Output
For each case,print a line include integers.The
i-th integer x show that the rank of x-th operating is
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
/**
hdu5386 模拟
题目大意：给一个棋盘涂色。每次操作给棋盘的某一列或一行涂上一种颜色，给定初始棋盘状态和终于棋盘状态，和一系列操作，请给这些序列排一个顺序
解题思路：初始棋盘事实上并没有什么用。我们从终于棋盘入手，每次找到一行或一列颜色所有一样的。如给定操作中有给这一行的如此操作，那么给此操作入队。
依次下去得到一个顺序，输出就可以
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int maxn=105;
int a[maxn][maxn],n,m,x,y;
int judge[maxn*5],flag[maxn*5],num[maxn*5];
vector<pair<int,int> >x_vec[105],y_vec[105];
char s[10];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
int x;
for(int i=0; i<n*n; i++)scanf("%d",&x);
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++)
{
x_vec[i].clear();
y_vec[i].clear();
}
for(int i=1; i<=m; i++)
{
scanf("%s%d%d",s,&x,&y);
if(s[0]==‘H‘)
{
x_vec[x].push_back(make_pair(y,i));
}
else
{
y_vec[x].push_back(make_pair(y,i));
}
}
memset(judge,0,sizeof(judge));
int t=m;
while(t)
{
int ok=0;
for(int i=1; i<=n; i++)
{
int sum=0,cnt=0;
memset(flag,0,sizeof(flag));
for(int j=1; j<=n&&sum<=1; j++)
{
if(a[i][j]==0)continue;
if(!flag[a[i][j]])
{
flag[a[i][j]]=1;
sum++;
cnt=a[i][j];
}
}
if(sum==1)
{
int len=x_vec[i].size();
for(int j=0; j<len; j++)
{
if(x_vec[i][j].first==cnt)
{
ok=1;
num[t--]=x_vec[i][j].second;
judge[x_vec[i][j].second]=1;
break;
}
}
for(int j=1; j<=n; j++)
a[i][j]=0;
}
sum=0,cnt=0;
memset(flag,0,sizeof(flag));
for(int j=1; j<=n&&sum<=1; j++)
{
if(a[j][i]==0)continue;
if(!flag[a[j][i]])
{
flag[a[j][i]]=1;
sum++;
cnt=a[j][i];
}
}
if(sum==1)
{
int len=y_vec[i].size();
for(int j=0; j<len; j++)
{
if(y_vec[i][j].first==cnt)
{
ok=1;
num[t--]=y_vec[i][j].second;
judge[y_vec[i][j].second]=1;
break;
}
}
for(int j=1; j<=n; j++)
a[j][i]=0;
}
}
if(ok==0)break;
}
for(int i=1; i<=n; i++)
{
int len=x_vec[i].size();
for(int j=0; j<len; j++)
{
if(judge[x_vec[i][j].second]==0)
num[t--]=x_vec[i][j].second;
}
len=y_vec[i].size();
for(int j=0; j<len; j++)
{
if(judge[y_vec[i][j].second]==0)
num[t--]=y_vec[i][j].second;
}
}
for(int i=1; i<=m; i++)
{
printf(i==m?"%d\n":"%d ",num[i]);
}
}
return 0;
}
hdu5386 棋盘涂色模拟
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。