注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

bcs  

2016-04-18 16:50:13|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

        farmer john 认为他们家需要更多的装饰品。在访问本地的中国商店时,他找到了一个他想采购且可以十分合适地放在他的壁炉上的易损的玻璃奶牛。

        这个奶牛饰品的形状是用一个N*N的字符矩阵描述的(如下图)。图中字符‘#’是奶饰品的一部分而字符‘.’则不是。

        ...............

        ...............

        ...............

        #..#...........

        ####...........

        ############...

        .##.#########..

        ....#######.##.

        ....##...##....

        ....##...##....

        ...............

        ...............

        ...............

        ...............

        ...............

    不幸的是,正当FJ可以买下这件饰品时,一只公牛冲过这家商店且打碎了FJ的饰品和柜中的不少饰品。FJ的饰品裂成了2半,且很快在总共K个洒落在地上的碎片之中被混淆了。每一个K中的碎片都用一个N*N的字符矩阵描述,就像原来那个饰品。

    请帮助FJ算出哪两个K中的碎片是他需要重新拼合在一起的。幸运的是,他的饰品的碎片在掉在地上后并没有翻转。所以FJ只需要将碎片水平地或垂直地拼合在一起,使它们紧密结合。如果他找到了这两个正确的碎片,他可以用任意上述的一种方法让它们重新构成原来的饰品。原来的饰品中的每一个‘#’都代表着两个碎片中的确切的‘#’(意思就是这两个碎片在拼合的过程中,不应当有任何的‘#’重叠,且和原饰品完全一样)

    当任何一个碎片中的‘#’漏出原来的N*N矩阵时,碎片不可以被拼合。每一个碎片的形状不一定要和其他‘#’连在一起。尽管如此,如果有一个碎片的形状是支离破碎的,它也一定要和原来的饰品中的一部分对应才可以拼合。

    输入:

    第一行是NK两个数。接下来的N行描述的是原来饰品的形状。再接下来的K*N行描述的是每一个碎片。

    输出:

    输出两个可以组成原来饰品的碎片的编号(两个从1k的整数)保证有解。两个输出的数字必须以从小到大排序。

===============================================================
        像我这样热爱暴力的人,果断写了一个暴力枚举(六重循环!!!):
        for ........... 枚举第一个碎片(10次)
         for ........... 枚举第二个碎片(10次)
         {
          裁剪第一幅图,使之移到左上角(64次)
          裁剪第二幅图,使之移到左上角(64次)
          for ........... 枚举相接位置的横坐标(8次)
           for ........... 枚举相接位置的纵坐标(8次)
            与目标做判断(64次)
         }
        搞定!
        然而程序会很恶心;
        然而白金组的升级版变态得都不想说了。
===============================================================

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>

#define For for (int i=1; i<=N; i++) for (int j=1; j<=N; j++) //恶心宏定义,跟神犇学的。
#define SC(x) for (int i=1; i<=N; i++) { for (int j=1; j<=N; j++) cout<<x.a[i][j]; cout<<endl; }

using namespace std;

int N;

struct Tmap //恶心结构体
{
int a[50][50];

void clean() { memset(a,0,sizeof a); }

void SR()
{
For { char ch; cin>>ch; if (ch=='#') a[i][j]=1; }
}
};

Tmap f;
Tmap z[11];

void Move(Tmap &x) //恶心裁剪(对齐左上角)
{
int xx,yy;

int xx1=0,xx2=0,yy1=0,yy2=0;

int ff=0;

For
{
if (x.a[i][j]==1 && ff==0)
{ xx1=i; yy1=j; ff=1; }
}

ff=0;

for (int j=1; j<=N; j++)
for (int i=1; i<=N; i++)
{
if (x.a[i][j]==1 && ff==0)
{ xx2=i; yy2=j; ff=1; }
}

xx=min(xx1,xx2); yy=min(yy1,yy2);

For x.a[i][j]=x.a[i+xx-1][j+yy-1];
}

bool bj(Tmap x,Tmap y) //恶心比较
{
For
{
for (int k1=0; k1<=N+5; k1++) //枚举偏移量
{
for (int k2=0; k2<=N+5; k2++) //枚举偏移量
{
int ff=0;

Tmap t=x;

For t.a[i+k1][j+k2]+=y.a[i][j];

For if (t.a[i][j]!=f.a[i][j]) ff=1;

if (ff==0) return true;
}
}
}

return false;
}

int main()
{
freopen("bcs.in","r",stdin);
freopen("bcs.out","w",stdout);

int K; cin>>N>>K;

f.clean();

For { char ch; cin>>ch; if (ch=='#') f.a[i][j]=1; }

Move(f);

for (int k=0; k<K; k++)
{
z[k].clean();
For { char ch; cin>>ch; if (ch=='#') z[k].a[i][j]=1; }
}

for (int k=0; k<K; k++) Move(z[k]);

for (int i=0; i<K; i++) //枚举
for (int j=0; j<K; j++)
if (i!=j && bj(z[i],z[j]) )
{ cout<<min(i,j)+1<<" "<<max(i,j)+1; return 0; }

return 0;
}


  评论这张
 
阅读(4)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018