看到这个题第一反应就是USACO第5章的那个题目。。又感觉差的有点远，想top想了半天结果被各种小情况绕昏了。。于是乎怒从心头起，恶向胆边生——丑陋的穷举了。。
枚举坐标x,y 矩形边长a
每次找一个完整的矩形（没有被任何覆盖），将其所有点标为通过（我是用‘0’表示的），下次找时，遇到0的也算合法，但是一个矩形至少得有一个点
ok记录矩形是否存在 ko记录是否有不为‘0’的点
#include<stdio.h>
long a1,b1,a2,b2,ok,i,j,k,have,ko,top,l;
long i1,i2,i3,i4,i5,i6;
int map[21][51];
int ans[2001][4];
void show()
{
int i,j;
for (i=1;i<=20;i++)
{
for (j=1;j<=50;j++)
printf("%c",map[i][j]);
printf("\n");
}
}
void search(long i,long j,char c)
{
long k;
long jia;
jia=1;
switch(c)
{
case 'd':k=i+1;
while (map[k][j]==i5 || map[k][j]=='0')
{
jia++;
if (map[k][j]==i5)
ko=0;
if (jia==l)
break;
k++;
}
if (jia<l)
jia++;
if ((map[k][j]==i4 || map[k][j]=='0') && jia==l)
{
if (map[k][j]==i4)
ko=0;
a2=k;
b2=j;
if (a2-a1!=b2-b1)
{
ok=1;
return;
}
search(k,j,'l');
}
else
ok=1;
break;
case 'u':k=i-1;
while (map[k][j]==i5 || map[k][j]=='0')
{
jia++;
if (map[k][j]==i5)
ko=0;
if (jia==l)
break;
k--;
}
if (!(a1==k && b1==j))
{
ok=1;
return;
}
return;
break;
case 'r':k=j+1;
while (map[i][k]==i6 || map[i][k]=='0')
{
jia++;
if (map[i][k]==i6)
ko=0;
if (jia==l)
break;
k++;
}
if (jia<l)
jia++;
if ((map[i][k]==i2 || map[i][k]=='0') && jia==l)
{
if (map[i][k]==i2)
ko=0;
search(i,k,'d');
}
else
ok=1;
break;
case 'l':k=j-1;
while (map[i][k]==i6 || map[i][k]=='0')
{
jia++;
if (map[i][k]==i6)
ko=0;
if (jia==l)
break;
k--;
}
if (jia<l)
jia++;
if ((map[i][k]==i3 || map[i][k]=='0') && jia==l)
{
if (map[i][k]==i3)
ko=0;
search(i,k,'u');
}
else
ok=1;
break;
}
}
int main()
{
i1=218;i2=191;i3=192;i4=217;i5=179;i6=196;
for (i=1;i<=20;i++)
{
for (j=1;j<=51;j++)
{
scanf("%c",&map[i][j]);
if (map[i][j]!='.' && map[i][j]!='\n')
{
have++;
}
else if (map[i][j]=='\n')
{
for (k=j;k<=50;k++)
map[i][j]='.';
break;
}
}
}
while (have!=0)
{
for (i=1;i<=20;i++)
for (j=1;j<=50;j++)
{
if (map[i][j]==i1 || map[i][j]=='0')
{
a1=i;b1=j;
for (l=1;l<=20;l++)
{
ok=0;ko=1;
if (map[i][j]==i1)
ko=0;
search(i,j,'r');
if (ok+ko==0)
{
top++;ans[top][1]=a1;ans[top][2]=b1;ans[top][3]=b2-b1+1;
for (k=a1;k<=a2;k++)
{
if (map[k][b1]!='0')
{
map[k][b1]='0';
have--;
}
if (map[k][b2]!='0')
{
have--;
map[k][b2]='0';
}
}
for (k=b1;k<=b2;k++)
{
if (map[a1][k]!='0')
{
map[a1][k]='0';
have--;
}
if (map[a2][k]!='0')
{
map[a2][k]='0';
have--;
}
}
}
}
}
}
}
printf("%d\n",top);
for (i=top;i>=1;i--)
printf("%d %d %d\n",ans[i][2]-1,ans[i][1]-1,ans[i][3]);
}
不是0。记录结果。
穷举啊~穷举啊~ 等到有一天所有的点都是‘0’和‘。’就可以输出结果了。。
有个地方要注意 解的正方形的数量和位置是不唯一的，只要你的答案能够得到要的图案就行。
posted on 2011-06-27 17:11
梦转千寻 阅读(128)
评论(0) 编辑 收藏 引用