hdu5386 棋盘涂色模拟

http://acm.hdu.edu.cn/showproblem.php?pid=5386

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

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;
}