首页 > 其他 > 详细

zoj3780 Paint the Grid Again 拓扑排序模拟

时间:2014-05-07 03:28:34      阅读:345      评论:0      收藏:0      [点我收藏+]

比赛时候看完题目就觉得是拓扑排序,当时心里隐隐觉得跟相框叠加那个题有点相似的

然后wzy问我no solution 是什么情况,我就一直去想是不是构成了什么排列就一定是no solution

其实只用再参考相框叠加那个题往前想一丁点就够了,就是从最后涂的那一层开始往前找,每一次都必然有一行或一整列是一样的

每次按逆字母序删除这一行或列就是了。

拓扑排序的题总是类似而且简单的,找到关系,敲代码完全不存在问题。


#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll long long
#define mod 1000000007
using namespace std;

struct node
{
    char dir;
    int index;
}ans[1010];

int r[510],c[510],n;
char mp[510][510];

bool ok()
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(mp[i][j]!=‘.‘)
                return 1;
    return 0;
}

int main()
{
    int t,i,j,flag,cnt;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%s",mp[i]);
        memset(c,0,sizeof c);
        memset(r,0,sizeof r);
        cnt=0;flag=1;
        while(ok())
        {
           /* for(i=0;i<n;i++,putchar(‘\n‘))
                for(j=0;j<n;j++)
                    putchar(mp[i][j]);*/
            //从最后一次操作开始找 要使顺序是字母序 那么倒着找就是逆字母序
            //因此 先R后C 从右下到左上

            if(flag==0) break;//没找到符合的行列 且整个没有结束
            for(i=n-1;i>=0;i--)
            {
                if(r[i]) continue;
                flag=1;
                for(j=0;j<n;j++)
                {
                    if(c[j]) continue;
                    if(mp[i][j]!=‘X‘)
                    {
                        flag=0;
                        break;
                    }
                }
                if(flag)
                {
                    for(j=0;j<n;j++)
                        mp[i][j]=‘.‘;
                    r[i]=1;
                    ans[cnt].dir=‘R‘;
                    ans[cnt].index=i+1;
                    cnt++;
                    break;
                }
            }
            if(flag) continue;

            for(i=n-1;i>=0;i--)
            {
                if(c[i]) continue;
                flag=1;
                for(j=0;j<n;j++)
                {
                    if(r[j]) continue;
                    if(mp[j][i]!=‘O‘)
                    {
                        flag=0;
                        break;
                    }
                }
                if(flag)
                {
                    for(j=0;j<n;j++)
                        mp[j][i]=‘.‘;
                    c[i]=1;
                    ans[cnt].dir=‘C‘;
                    ans[cnt].index=i+1;
                    cnt++;
                    break;
                }
            }
        }
        if(flag)
        {
            for(i=cnt-1;i>0;i--)
                printf("%c%d ",ans[i].dir,ans[i].index);
            printf("%c%d\n",ans[i].dir,ans[i].index);
        }
        else printf("No solution\n");
    }
    return 0;
}


zoj3780 Paint the Grid Again 拓扑排序模拟,布布扣,bubuko.com

zoj3780 Paint the Grid Again 拓扑排序模拟

原文:http://blog.csdn.net/u011032846/article/details/25026325

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!