[ACM] POJ1021解题报告

127 Replies

这是一道.. 怎么说呢 只能用龌龊来形容的题目..

折腾了两天, 重写了两遍, 第一次在题目里用链表, 有点为难自己的意思, 不过确实暂时还没想到其他可以省空间的办法.

思路:

1. 每一块用一个节点存储, 存储方式我用的点阵..   先随便找出一个点 然后dfs搜出这个点所在的区域

2. 每一块cake正过来反过来各转4个90度, 用从上到下从左到右一个点一个点比过去这样来排序, 有点傻不过还没发掘出什么具有[旋转不变性]的数学方法可以算出方向不同的cake的特征.

3. 选出8个方向(360度/90度*翻转的2面)最大的cake存储

细节:

1. 排序用qsort就很方便

2. 用了个format()把cake仅靠坐标系,这样sort()过后cake之间的比较是数组里元素一一对应的比较

刚刚好250行.. 不是说前两页1009是最恶心的吗..被骗了..

[cpp]#include <iostream>
#include <string.h>
#include <stdlib.h>

using namespace std;

typedef struct coo {
int x,y;
} Coo;

typedef struct cake {
Coo a[10000];
int n,amount;
struct cake *next;
} Cake;

int t,n,w,h;
Coo a1[10000],a2[10000];
bool cherry[100][100];
Cake *newpiece,*a1cake,*a2cake;

int comp(const void *a,const void *b) {
int t;
if((t=(*(Coo *)a).y-(*(Coo *)b).y)!=0)
return -t;
return (*(Coo *)a).x-(*(Coo *)b).x;
}

void dfs_init(Coo *a) {
for(int i=0;i<w;i++)
for(int j=0;j<h;j++)
cherry[i][j]=false;
for(int i=0;i<n;i++)
cherry[a[i].x][a[i].y]=true;
return;
}

Cake *dfs() {
Cake *bake;
int m1,m2;
bake=(Cake *)malloc(sizeof(Cake));
bake->n=bake->amount=0;
for(int i=0;i<w;i++)
for(int j=0;j<h;j++)
if(cherry[i][j]) {
bake->a[0].x=i;
bake->a[0].y=j;
cherry[i][j]=false;
bake->n++;
i=w;
break;
}
if(bake->n==0)
return NULL;
m1=0;
m2=1;
while(m1!=m2) {
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++) {
if((i+j==1||i+j==-1)&& bake->a[m1].x+i>=0 && bake->a[m1].x+i<w &&
bake->a[m1].y+j>=0 && bake->a[m1].y+j<h &&
cherry[bake->a[m1].x+i][bake->a[m1].y+j]) {
bake->a[m2].x=bake->a[m1].x+i;
bake->a[m2].y=bake->a[m1].y+j;
m2++;
cherry[bake->a[m1].x+i][bake->a[m1].y+j]=false;
}
}
m1++;
}
bake->n=m2;
return bake;
}

// This produces a new rotated cake
void rotate(Cake *&a) {
int x;
for(int i=0;i<a->n;i++) {
x=a->a[i].x;
a->a[i].x=a->a[i].y;
a->a[i].y=-x;
}
return;
}
void roll(Cake *&a) {
for(int i=0;i<a->n;i++)
a->a[i].x*=-1;
return;
}

void format(Cake *f) {
Coo corner;
qsort((void *)(f->a),f->n,sizeof(Coo),comp);
corner=f->a[0];
for(int i=1;i<f->n;i++)
if(corner.x>f->a[i].x)
corner.x=f->a[i].x;
for(int i=0;i<f->n;i++) {
f->a[i].x-=corner.x;
f->a[i].y-=corner.y;
}
return;
}

// Cake p1 and p2 should have been sorted. otherwise can’t do comparing
bool isBigger(Cake *p1,Cake *p2) {
int t;
for(int i=0;i<p1->n;i++) {
t=comp((void *)(p1->a+i),(void *)(p2->a+i));
if(t<0)
return true;
if(t>0)
return false;
}
return false;
}

//always sort *newpiece.
void sort()
{
Cake *tbc,*temp; //The Biggest Cake =D
tbc=newpiece;
format(tbc);
temp=(Cake *)malloc(sizeof(Cake));
*temp=*tbc;
for (int i=2;i<=8;i++) {
if(i==5)
roll(temp);
else
rotate(temp);
format(temp);
if(isBigger(temp,tbc)) {
*tbc=*temp;
}
}
free(temp);
newpiece=tbc;
}

/* isCakeALie: Search matched cake in the list.
Input: global variable *a1cake and *newpiece
Output: If there is a match, output a pointer to the cake(in the list), otherwise
return NULL; */
Cake *isCakeALie() {
int i;
Cake *p;
p=a1cake;
while(p) {
if(p->n==newpiece->n) {
for(i=0;i<p->n;i++)
if(p->a[i].x!=newpiece->a[i].x||p->a[i].y!=newpiece->a[i].y)
break;
if(i==p->n)
break;
}
p=p->next;
}
return p;
}

//seal newpiece into a1cake
void seal() {
Cake *pos;
if(pos=isCakeALie()) {
pos->amount++;
free(newpiece);
return;
}
pos=a1cake;
a1cake=newpiece;
newpiece->next=pos;
a1cake->amount=1;
return;
}

//eat one cake at one time in *a1cake
bool fuck() {
Cake *pos,*temp;
pos=isCakeALie();
free(newpiece);
if(pos==NULL)
return false;
if(pos->amount==1) {
if(a1cake==pos) {
a1cake=a1cake->next;
free(pos);
return true;
}
for(temp=a1cake;temp->next!=pos;temp=temp->next);
temp->next=pos->next;
free(pos);
return true;
}
pos->amount–;
return true;
}

int main()
{
bool okay;
Cake *temp;
cin>>t;
while (t–) {
cin>>w>>h>>n;
for (int i=0;i<n;i++)
cin>>a1[i].x>>a1[i].y;
for (int i=0;i<n;i++)
cin>>a2[i].x>>a2[i].y;

a1cake=NULL;
dfs_init(a1);
while (1) {
newpiece=dfs();
if (!newpiece)
break;
sort();
seal();
}

dfs_init(a2);
okay=true;
while (1) {
newpiece=dfs();
if (!newpiece)
break;
sort();
if (!fuck()) {
okay=false;
free(newpiece);
break;
}
//free(newpiece); Do it inside fuck()
}
if (a1cake)
okay=false;
if (okay)
cout<<"YES\n";
else
cout<<"NO\n";
while(a1cake) {
temp=a1cake;
a1cake=a1cake->next;
free(temp);
}
}
return 0;
}
[/cpp]

127 thoughts on “[ACM] POJ1021解题报告”

Leave a Reply

Your email address will not be published. Required fields are marked *