USACO 4.4.3 Frame Up

中文题意
chapter 4 over了,接下来chapter 5了,争取1周完成,最迟不能超过2周,一共也才18题,而且凸包还是以前学过的,应该就启发式搜索没用过.加油.over了usaco就做sgu加专题吧,go go go!!!
此题是一个top排序的问题,不过需要按字典序输出所有可能的顺序.首先说下为什么是top排序的问题:对每个图像,如果在最后这个图像的某个点被覆盖了,那么被覆盖的这个图像一定在覆盖的这个图像的前面,这样就可以确定一系列顺序了,而这恰恰符合top排序.至于输出所有可能的顺序,而且还要按字典序,一开始我想用层次图一样的东西来搞,首先算出每个点的层次,然后对每个层次全排列,以为这样可以得到所有的顺序了,可是我没有考虑有些点是可以在多个层次的比如下面的例子:1->2;4->2;3->4那么1就可以和3在一个层次也可以和4在一个层次,这样就很复杂了.就上网搜了一个,程序框架如下
void print(Graph g,int l)
if(g中没有点了)
输出队列中的顺序
else
if(g没有入度为0的点)
g有环无法top排序
else
for(按顺序取g中入度为0的点)
入队列 从图中”删除”这个点以及和这个点有关的所有边
print(l+1)
还原这个点以及所有和这个点有关的边
这样就能够输出所有的顺序,而且还是按字典序排好序的.本题代码如下:

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

char frame[36][36];
int H,W
int graph[30][200];
int top[30],buttom[30],left[30],right[30];
int total
int num[30];
int cmp(const void a,const void b)
{
if(((int )a) > ((int )b))
return 1
if(((int )a) < ((int )b))
return -1
return 0
}
void print(int idx)
{
int i,j,k,tmp
int del[30][2],i_del
if(idx==total)
{
for(i=0i<idx;i++)
printf(“%c”,num[i]+‘A’);
printf(“\n“);
}
else
{
for(i=0i<26;i++)
{
if(-1 != buttom[i] & 0 == graph[i][0])
{
num[idx]=i
buttom[i]=-1//“删除这个点”
i_del=0
for(j=0j<26;j++)
{
for(k=1k<=graph[j][0];k++)
{
if(i==graph[j][k])
{//“删除”和这个点有关的边
graph[j][k]=graph[j][graph[j][0]];
graph[j][graph[j][0]]=i
graph[j][0]–
del[i_del][0]=j
del[i_del][1]=k
i_del++
break
}
}
}
print(idx+1);
for(j=0j<i_del;j++)
{
graph[del[j][0]][0]++
tmp=graph[del[j][0]][del[j][1]];
graph[del[j][0]][del[j][1]]=graph[del[j][0]][graph[del[j][0]][0]];
graph[del[j][0]][graph[del[j][0]][0]]=tmp
}
buttom[i]=1//buttom[i]已经没实际意义了
}
}
}
}
void out_graph()
{
int i,j
for(i=0i<26;i++)
{
printf(“——-%d:”,i);
for(j=1j<=graph[i][0];j++)
printf(“(%d,%d,%d) “,i,j,graph[i][j]);
printf(“\n“);
}
}
void output()
{
int i
for(i=0i<26;i++)
{
if(-1 != buttom[i])
total++
qsort(graph[i]+1,graph[i][0],sizeof(graph[0][0]),cmp);
}
// out_graph();
print(0);
}
int main(void)
{
freopen(“frameup.in”,“r”,stdin);
freopen(“frameup.out”,“w”,stdout);
int i,j,k,i1
scanf(“%d%d%c”,H,&W);
/
(0,0) top
left right
buttom
(H-1,W-1)
/
memset(buttom,-1,sizeof(buttom));
memset(right,-1,sizeof(right));
for(i=0i<30;i++)
{
left[i]=top[i]=H+W
}
for(i=0i<H;i++)
{
for(j=0j<W;j++)
{
scanf(“%c”,frame[i][j]);
if(‘A’ <= frame[i][j] & ‘Z’ >= frame[i][j])
{
k=frame[i][j]-‘A’
if(i<top[k])
top[k]=i
if(j<left[k])
left[k]=j
if(i>buttom[k])
buttom[k]=i
if(j>right[k])
right[k]=j
}
}
scanf(“%c”);
}
memset(graph,0,sizeof(graph));
for(i=0i<26;i++)
{
if(-1 == buttom[i])
continue
//top buttom row
for(j=left[i];j<=right[i];j++)
{
if(‘A’<=frame[top[i]][j]&‘Z’>=frame[top[i]][j])
{
k=frame[top[i]][j]-‘A’
if(i!=k)
{
for(i1=1i1<=graph[k][0];i1++)
if(graph[k][i1]==i)
break
if(graph[k][0]+1==i1)
graph[k][++graph[k][0]]=i
}
}
if(‘A’ <= frame[buttom[i]][j] & ‘Z’ >= frame[buttom[i]][j])
{
k=frame[buttom[i]][j]-‘A’
if(i!=k)
{
for(i1=1i1<=graph[k][0];i1++)
if(graph[k][i1]==i)
break
if(graph[k][0]+1==i1)
graph[k][++graph[k][0]]=i
}
}
}
//left right col
for(j=top[i];j<=buttom[i];j++)
{
if(‘A’<=frame[j][left[i]] & ‘Z’ >= frame[j][left[i]])
{
k=frame[j][left[i]]-‘A’
if(i!= k)
{
for(i1=1i1<=graph[k][0];i1++)
if(graph[k][i1]==i)
break
if(graph[k][0]+1==i1)
graph[k][++graph[k][0]]=i
}
}
if(‘A’ <=frame[j][right[i]] & ‘Z’ >= frame[j][right[i]])
{
k=frame[j][right[i]]-‘A’
if(i != k)
{
for(i1=1i1<=graph[k][0];i1++)
if(graph[k][i1]==i)
break
if(graph[k][0]+1==i1)
graph[k][++graph[k][0]]=i
}
}
}
}
output();
return 0
}

Comments

2011-03-22
▲