USACO 5.1.2 Starry Night

中文题目
直接枚举就行了,主要是判重的问题,也就是说要判断那些图形是出现过的,如果解决了这个问题,那么这题就基本没问题了.我的做法是,如果找到一个新图形,就把这个图形提出来,然后从前面的图形中去找,当然要考虑旋转和翻转了.这样就出现了,要写旋转了[翻转好写],我是把图形扩大到一个正方形,因为这样我觉得好写一点.然后旋转的时候,可以先在草稿纸上画一下,然后得到对应关系,然后每次旋转90°.一共旋转3次,得到4个不同的图形,加上翻转就变成了8次.基本就OK了,不过代码量还是有点的,代码如下:

/
ID:qcx97811
LANG:C
TASK:starry
/
#include
#include
#include
#include

char ori[106][106];
int H,W
int l,r,t,b;
int y[8]={1,1,0,-1,-1,-1,0,1};
int x[8]={0,1,1,1,0,-1,-1,-1};
char map[26][100+2][100+2];//26[100100]
char tmp[100+2][100+2];
int idx//now map index
int stars
void bfs(int _i,int _j)
{
int i,j
int rear,front
int q[168];
int now_i,now_j,to_i,to_j
front=-1
q[rear=0]=_iW+_j
ori[_i][_j]=2
l=r=_j
t=b=_i
stars=1
while(front < rear)
{
++front
now_j=q[front]%W
now_i=q[front]/W
for(i=0i<8;i++)
{
to_i=now_i+x[i];
to_j=now_j+y[i];
if(to_i<0||to_i>=H)
continue
if(to_j<0||to_j>=W)
continue
if(1==ori[to_i][to_j])
{
ori[to_i][to_j]=2
q[++rear]=to_iW+to_j
stars++
if(to_i<t)
t=to_i
if(to_i>b)
b=to_i
if(to_j<l)
l=to_j
if(to_j>r)
r=to_j
}
}
}
memset(tmp,0,sizeof(tmp));
for(i=ti<=b;i++)
{
for(j=lj<=r;j++)
{
tmp[i-t][j-l]=ori[i][j];
}
}
}
void rotate()
{//rotate the tmp 90°
int i,j,k
char c
char exchange[100][100];
for(i=0i<100;i++)
{
for(j=0j<100;j++)
{
exchange[i][j]=tmp[j][99-i];
}
}
for(i=0i<100;i++)
{
for(j=0j<100;j++)
tmp[i][j]=exchange[i][j];
}
//把图形移到左上角
for(i=0i<100;i++)
{
for(j=0j<100;j++)
{
if(2 == tmp[i][j])
break
}
if(100 != j)
break
}
for(k=0k<100-i;k++)
{
for(j=0j<100;j++)
tmp[k][j]=tmp[k+i][j];
}
for(;k<100k++)
for(j=0j<100;j++)
tmp[k][j]=0
for(i=0i<100;i++)
{
for(j=0j<100;j++)
{
if(2 == tmp[j][i])
break
}
if(100 != j)
break
}
for(k=0k<100-i;k++)
{
for(j=0j<100;j++)
tmp[j][k]=tmp[j][k+i];
}
for(;k<100k++)
for(j=0j<100;j++)
tmp[j][k]=0
}
int test(int _idx)
{
int i,j
int loop=0
int tstars=stars
for(loop=0loop<4;loop++)
{
tstars=stars
for(i=1i<=map[_idx][0][0];i++)
{
for(j=1j<=map[_idx][i][0];j++)
{
if(1==map[_idx][i][j]&2==tmp[i-1][j-1])
{
tstars–
}
}
}
if(0 == tstars)
return 1
//水平翻转
tstars=stars
for(i=1i<=map[_idx][0][0];i++)
{
for(j=1j<=map[_idx][i][0];j++)
{
if(1==map[_idx][i][j] & 2 == tmp[map[_idx][0][0]-i][j-1])
tstars–
}
}
if(0 == tstars)
return 1
rotate();
}
return 0
}
int find()
{
int i,j,i1,j1
int t_stars=stars
for(i=0i<idx;i++)
{
t_stars=stars
if(t_stars != map[i][0][1])//num of stars isn’t equal
continue
#if 1
if(1==test(i))
{
return i
}
#endif
}
#if 1
map[idx][0][0]=b-t+1
map[idx][0][1]=stars
for(i=1i<=map[idx][0][0];i++)
{
map[idx][i][0]=r-l+1
for(j=1j<=map[idx][i][0];j++)
{
if(0==ori[i+t-1][j+l-1] || 1==ori[i+t-1][j+l-1])
map[idx][i][j]=0
else
map[idx][i][j]=1
}
}
#endif
return -1
}
int main(void)
{
freopen(“starry.in”,“r”,stdin);
freopen(“starry.out”,“w”,stdout);
int i,j,k
int i1,j1
int flag
scanf(“%d%d%*c”,W,&H);
for(i=0i<H;i++)
{
for(j=0j<W;j++)
{
scanf(“%c”,ori[i][j]);
ori[i][j] = ori[i][j]-‘0’
}
getchar();
}
#if 0
for(i=0;i
{
for(j=0;j
printf(“%c”,ori[i][j]);
printf(“\n”);
}
#endif
idx=0
for(i=0i<H;i++)
{
for(j=0j<W;j++)
{
if(1==ori[i][j])
{
bfs(i,j);
flag=find();
if(-1 != flag)
{
k=flag+‘a’
}
else
{
k=idx+‘a’
idx++
}
for(i1=ti1<=b;i1++)
for(j1=lj1<=r;j1++)
{
if(2==ori[i1][j1])
ori[i1][j1]=k
}
}
}
}
for(i=0i<H;i++)
{
for(j=0j<W;j++)
{
if(0==ori[i][j])
printf(“0”);
else
printf(“%c”,ori[i][j]);
}
printf(“\n“);
}
memset(tmp,0,sizeof(tmp));
#if 0
tmp[0][1]=2;
tmp[1][1]=2;
tmp[2][0]=2;
rotate();
printf(“———————\n”);
for(i=0;i<100;i++)< span="">
{
for(j=0;j<100;j++)< span="">
printf(“%c”,tmp[i][j]+’0’);
printf(“\n”);
}
#endif
return 0
}

Comments

2011-03-27
▲