HDU 5386 Cover

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5386

题目大意：给一个初始矩阵（n×n）、一个目标矩阵(n×n)和m个操作，要求找到一种操作顺序，使初始矩阵变成目标矩阵。操作共有两种，如下：

　　L x y: 把当前矩阵第x列的数全变为y
　　H x y: 把当前矩阵第x行的数全变为y

输入格式：先输入case数T，每个case第一行是两个整数n和m，接下来n行输入初始矩阵，再下来n行输入目标矩阵。最后m行输入操作。
　　1≤color[i][j]≤n，color[i][j]为数组元素。
　　T=5
　　1≤n≤100
　　1≤m≤500

分析：根据数据范围推解题方法，此题对数组元素的大小做了限制，可以从这点下手。

　　统计目标矩阵中每个数出现的次数，对列亦是。若有个操作是L x y，而目标矩阵第x列的值全是y，那显然，这个操作最后一次做是合情合理的，去掉这一列后，又是一个新问题，可以找到新的可以“最后一步”做的操作。依次类推，每次找一个合法的操作，逆序输出即可。

参考代码：

主体代码是队友写的，写的够简洁的~

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

struct node{

    int t,x,y;

}b[];

int c[][][],a[][],mark[],ans[],ans2[];

char s[];

bool vis[][];

int main(){

    int t,n,m;

    scanf("%d",&t);

    while(t--){

        scanf("%d%d",&n,&m);

        for(int i=;i<n;i++)

            for(int j=;j<n;j++)

                scanf("%d",&a[i][j]);

        memset(c,,sizeof(c));

        memset(mark,,sizeof(mark));

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

            {

                scanf("%d",&a[i][j]);

                c[][j][a[i][j]]++;

                c[][i][a[i][j]]++;

            }

        int cnt=,d[];

        d[]=n;

        d[]=n;

        for(int i=;i<m;i++){

            scanf("%s%d%d",&s,&b[i].x,&b[i].y);

            if(s[]=='L') b[i].t=;

                else b[i].t=;

        }

        memset(vis, , sizeof(vis));

        for(int j=;j<m;j++)

            for(int i=;i<m;i++)

            if(!mark[i]){

                if(d[b[i].t]==c[b[i].t][b[i].x][b[i].y])

                {

                    if(vis[b[i].t][b[i].x]) continue;

                    vis[b[i].t][b[i].x] = ;

                    mark[i]=;

                    ans[m-cnt-]=i+;

                    cnt++;

                    d[b[i].t^]--;

                    for(int k=;k<=n;k++){

                        if(vis[b[i].t^][k]) continue;

                        if(b[i].t) c[b[i].t^][k][a[b[i].x][k]]--;

                        else c[b[i].t^][k][a[k][b[i].x]]--;

                    }

                }

            }

        int flag=;

        for(int i=;i<m;i++)

            if(!mark[i]){

                ans[m-cnt-]=i+;

                cnt++;

            }

        for(int i=;i<m;i++){

            if(flag==) printf(" ");

            flag=;

            printf("%d",ans[i]);

        }

        puts("");

    }

}

巴特西

HDU 5386 Cover

最新文章

热门文章