首页 > 代码库 > hdu5386 棋盘涂色模拟

hdu5386 棋盘涂色模拟

2024-09-20 21:50:31   208人阅读

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.
 

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




 

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 棋盘涂色模拟


联系
我们