USACO

2011-08-29
USACO 5.4&5.5

今天终于把第5章搞定了.USACO还剩下3题,早日结束了这3题,任务还很艰巨啊.

简单写下这两节的题解.这两节搞了好久啊.有些题还是看了题解之后,然后差不多是照着标称打的(- -|).

ALL Latin:比较变态的一道搜索题,7的时候过不去,然后看的题解,那个循环群什么的不是很懂,用的是另外一种方法,就是首先第一行第一列都放好(最后结果再乘以(n-1)!就行),然后第2行第2列放2,3,4,5的方案是一样多的.貌似比较慢,最慢的0.9+s

Canada Tour:费用流的方法没弄,用的是DP,类似方格取数的那种多线程DP,只需要看最后是不是有两条独立的路径从起点到终点就OK了,中间不能有重复的点

Character Recognition:很烦的一道题,借鉴标称的,方法:DP,有一点就是多余的那一行的变化数不算在里面的.然后如果知道了前i行的可以推知i+19,i+20,i+21的情况.

Betsy’s Tour:正解是连通性DP?czw和我说了下这是最简单的连通性DP,但是那论文看不懂,刚好这题可以搜过,只需要考虑下,如果进入了死胡同就不要搜了,还有如果当前的路径把格子分成了两边就不用搜了.死胡同那个可以考虑做过这个点之后,它的上下左右点是否被走过,一个点必须有进有出才行(不然进死胡同了),除了起点和终点

TeleCowmunication:拆点,最大流,然后枚举删点.拆点时,每个点拆成2i,2i+1,然后流量是1,原边中有边的则加两条无穷大的边,跑最大流,然后枚举删点.看删掉点之后是不是最大流减少了.是的话就输出这个点,最大流减少,继续枚举

Picture:很早以前就听说这题是线段树的好题,但是我还是用了朴素的方法(小汗一下),直接把横向边和纵向边分别排序,然后遇到起始边(坐标小的)就+1.否则-1.这样如果由0->1,那么一定是最终矩形的边,这样枚举完了之后,在USACO还挺快.线段树就是在更新+1,-1的时候用线段树,可以做到区间处理.降低时间复杂度

Hidden Passwords:刚好czw和我说过最小表示法,然后就直接做了.或许这是这两节我觉得最简单的了- -|.貌似还有很多其他方法,可以看看nocow的分析

Two Five:就是一个一个算就行了.主要是要好写,而且速度还过得去.对于数变字符串.可以枚举25个位置,如果某个位置放字符ch的数目加上前面算的结果已经超过了给的n,那么就把这个位置放置ch,因为放置ch-1的时候不够,然后接着放下一个位置,直到25个位置全放好为止,字符串变数字的差不多,只不过把上面的操作反过来而已,就是看这个字符之前有多少个.比如求ACD的,那么我们就求ABC,ABD,ACB,的方案数,然后再求ACD后面有多少个,就像求10进制数的大小一样,求521是第几个,可以首先求1,2,3,4的个数,然后求5_(<2)和52(<1)的个数,最后结果+1就是521的结果了

接下来还有三题,搞定也算是圆满了USACO,加油吧

2011-04-10
USACO 5.3.4Big Barn

中文题意
此题我用的是dp做的,因为数据不大,所以直接开两个二维数组,一个记录农场信息,一个是dp用的矩阵.dp[i][j]表示右下角是[i,j]的正方形的边长.我的农场信息是,farm[i][j]=1表示无树 而=0表示有树.那么dp的二维数组首先初始化第一行和第一列,如果第一行的某个点有树,那么这个点的dp值为0,否则为1.递推方程是dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1[if farm[i][j]==1]否则dp[i][j]=0;然后输出dp的最大值就OK了.当然这里dp的二维数组完全没必要,因为dp[i][j]只与当前行,上一行有关,我们完全可以只开一个2*N的数组就ok了.

2011-04-10
USACO 5.2.3 Wisconsin Squares

中文题意
这题首先看到的是时限:5S.这么长的时间,我们可以暴力啦.一顿暴搜就OK了.其中注意几点:I.那个顺序,是一个一个比的,而不是先把所有的类型比较,然后row比较,最后col比较.一开始我是按后面的排序搞的,结果sample都过不去.sample的输出是E 2 1;E 2 3;D 1 4 我的输出是E 2 3;D 1 4;E 2 1.可以看出后面这组数据是把类型,row,col分开比较.但是这样是不对的.所以应该同时比较一个步骤的类型,row,col.II.如果放置的小牛不可以被移出去[因为一共16次完成移动],移动的时候周围不可以有相同类型的牛.III.最后注意看牛群数目是否一样,即3A 3B 3C 4D 3E.IV.最重要的的是.这题非常操蛋啊.数据就一组.而且就是sample.这个让我蛋疼不已啊.下面附上我的代码:[那个解可以不更新,因为每次都是按顺序找的.所以第一个解肯定是最有解]

/
ID:qcx97811
LANG:C
TASK:wissqu
/
#include
#include
#include
#include
char cow[66];//原矩阵
char goal[6]={3,3,3,4,3};//最终牛群
char now[6],num[6];//now是搜索结束时的牛群数 num是当前的牛群数
char used[66];//某个点是否已经是小牛了,也就是不可以换出去
typedef struct
{//结构体,c表示字符 n_r表示row n_c表示col
char c
char n_r,n_c
}Node
Node way[18],best[18];//best表示最有解 way是搜索的中间解
int sum//sum是总结过数
int idx
void check_best()
{//检查best 然后更新est
char s1[18],s2[18];
int i,j
int k
for(i=0i<16;i++)
{
if(best[i].c < way[i].c)
return ;
if(best[i].c == way[i].c)
{
if(best[i].n_r < way[i].n_r)
return ;
if(best[i].n_r == way[i].n_r)
{
if(best[i].n_c <= way[i].n_c)
return
break
}
else
break
}
else
{
break
}
}
for(i=0i<16;i++)
{
best[i]=way[i];
}
}
int can_place(int r,int c,char ch)
{//可以把ch放置在 [r,c]这个点上
int i,j
if(1==used[r4+c])
return 0
for(i=r-1i<r+2;i++)
{
if(i>=0&i<4)
{
for(j=c-1j<c+2;j++)
{
if(j>=0&j<4)
{
if(ch == cow[i4+j])
return 0
}
}
}
}
return 1
}
void search(int level)
{
int i,j
int r,c
char ch
if(level>16)
{//已经操作16次了
memset(now,0,sizeof(now));
for(i=0i<4;i++)
{
for(j=0j<4;j++)
{
now[cow[i4+j]-‘A’]++
}
}
for(i=0i<5;i++)
{
if(now[i] != goal[i])
break
}
if(5 != i)//牛群数目不对
return
if(0 == sum)
{
for(i=0i<16;i++)
best[i]=way[i];
}
else
{
check_best();
}
sum++
return ;
}
for(i=0i<5;i++)
{
if(num[i]>=goal[i])
continue//这种牛已经放置完成 不需要放置该种牛群
num[i]++
for(r=0r<4;r++)
{
for(c=0c<4;c++)
{
if(can_place(r,c,i+‘A’))
{
ch=cow[r4+c];
cow[r4+c]=i+‘A’
used[r4+c]=1
idx++
way[level-1].c=i+‘A’
way[level-1].n_r=r
way[level-1].n_c=c
search(level+1);
idx–//把刚才加进入

的字符串去掉
used[r4+c]=0
cow[4r+c]=ch
}
}
}
num[i]–
}
}
int main(void)
{
freopen(“wissqu.in”,“r”,stdin);
freopen(“wissqu.out”,“w”,stdout);
int i,j
for(i=0i<4;i++)
{
for(j=0j<4;j++)
scanf(“%c”,cow[i4+j]);
getchar();
}
#if 0
for(i=0;i<4;i++)< span="">
{
for(j=0;j<4;j++)< span="">
printf(“%c”,cow[i4+j]);
printf(“\n”);
}
#endif
sum=0
idx=0
memset(used,0,sizeof(used));
memset(num,0,sizeof(num));
search(1);
for(i=0i<16;i++)
{
printf(“%c %d %d\n“,best[i].c,best[i].n_r+1,best[i].n_c+1);
}
printf(“%d\n“,sum);
return 0
}

2011-04-07
USACO 5.2.2 Electric Fences

中文题意
这题首先是精读要求不高,只需要输出1位小数,然后范围不大,坐标是0-100.线段条数是150.我一开始想暴力搞,可是死在第7组上.死活过不了.然后去学校的群里问,热心人很多,不过没解决问题.在这里还是要感谢下他们的.然后去各大群里问,最囧的是很多人把线段看成直线,然后说”X和Y分开搞,然后不是显然么”,知道是线段后就说出了各种自己的方法,一开始我问了czw.他说可以模拟退火搞,那个时候我不知道模拟退火的一些细节,就没去试.后来在DIY群里,各大神牛说这数据,模拟退火肯定可搞.就试着去搞了下,发现模拟退火还是比较好写的,不过我总想着它不靠谱,总觉得可能不对,总想着会在中间某一步进入死胡同…..不过看了一些论文之后才有那么一点点感觉,反正是个RP问题[我还是顽固的这么认为],那么就拼拼RP吧.下面是官方的题解.也是模拟退火,不过个人觉得这个还是比较靠谱的.具体的模拟退火还是自己搜吧,大致过程就是不断的在当前最优点的领域节点中找一个最优点

/
/
#include
#include

#define FMAX 135
#define MOVES 50
#define IMAX 4

int numfence
FILE int,out
struct fence
double totaldist(double ,double);
void swap(int ,int &);

struct fence
{
int minx,maxx,miny,maxy
void setvals()
{
fscanf(in,“%d%d%d%d”,minx,&miny,&maxx,&maxy);
if(minx>maxx)
swap(minx,maxx);
if(miny>maxy)
swap(miny,maxy);
}
}feces[FMAX];

double totaldist(double x,double y)
{
int a
double ans=0,xdiff,ydiff
for(a=0a<numfence;a++)
{
if(fences[a].minx > x)
xdiff=fences[a].minx-x
else
{
if(fences[a].maxx<x)
xdiff=x-fences[a].maxx
else
xdiff=0
}
if(fences[a].miny>y)
ydiff=fences[a].miny-y
else
{
if(fences[a].maxy<y)
ydiff=y-fences[a].maxy
else
ydiff=0
}
answer += sqrt(xdiffxdiff + ydiffydiff);
}
return answer
}
void swap(int a,int &b)
{
int tmp=a
a=b;
b=tmp
}

int main(void)
{
in=fopen(“fence3.in”,“r”);
out=fopen(“fence3.out”,“w”);
int a,b,c,best
double elecx,elecy,xchange,ychange,tsum
double bestsum=100000.0
double xinc[IMAX],yinc[IMAx],pi
pi=acos(-1.0);
for(a=0a < IMAX;a++)
{
xinc[a]=cos(2pia/IMAX);
yinc[a]=sin(2pia/IMAX);
}
fscanf(in,“%d”,numfence);
for(a=0a<numfence;a++)
fences[a].setvals();
elecx=0
elecy=0
xchange=20
ychange=20
bestsum=totaldist(elecx,elecy);
for(b=1b<=MOVES;b++)
{
if(0==b%10)
{
ychange=ychange0.1
xchange=xchange0.1
}
best=-1
for(c=0c<IMAX;c++)
{
elecx += xchangexinc[c];
elecy += xchangeyinc[c];
tsum=totaldist(elecx,elecy);
if(tsum<bestsum)
{
bestsum=tsum
best=c
}
elecx -= xchangexinc[c];
elecy -= ychangeyinc[c];
}
if(-1 != best)
{
elecx += xchangexinc[best];
elecy += ychangeyinc[best];
}
bestsum=totaldist(elecx,elecy);
}
fprintf(out,“%.1f %.1f %.1f\n“,elecx,elecy,bestsum);
return 0
}

2011-03-30
USACO 5.2.1 Snail Trails

中文题目
这题主要是看懂题目的意思,一开始没看懂意思,导致错了两次,后来经过再次再再次的读题,才读懂了题目,题意是:首先选一个方向,然后一直走,如果遇到边界或者障碍物就停下来而且转90度,继续走,但是如果在这之间遇到已经走过的一个地点,那么就之间停止了,主要是后面这个直接停止,如果没看懂就悲剧了.一开始我就是把这看错了.看来还是英语要好好的才行阿.懂了题意之后就直接搜就行了.代码如下:

/
ID:qcx97811
LANG:C
TASK:snail
/
#include
#include
#include
#include
char grid[128][128];
int N,B;
int change_i[4]={-1,0,1,0};
int change_j[4]={0,1,0,-1};
int work(int _i,int _j,int dis)
{
int _x,_y
int tmp_x,tmp_y
int i
int ret,max
max=dis
for(i=0i<4;i++)
{
_x=_i
_y=_j
while(1)
{
_x+=change_i[i];
_y+=change_j[i];
if(2==grid[_x][_y])
{
if(abs(_x-_i)+abs(_y-_j)-1 > 0)
{
tmp_x=_i+change_i[i];
tmp_y=_j+change_j[i];
while(!((tmp_x==_x) & (tmp_y==_y)))
{
grid[tmp_x][tmp_y]=1
tmp_x+=change_i[i];
tmp_y+=change_j[i];
}
ret=work(_x-change_i[i],_y-change_j[i],dis+abs(_x-_i)+abs(_y-j)-1);
tmp_x=_i+change_i[i];
tmp_y=_j+change_j[i];
while(!((tmp_x==_x)&(tmp_y==_y)))
{
grid[tmp_x][tmp_y]=0
tmp_x+=change_i[i];
tmp_y+=change_j[i];
}
if(max<ret)
max=ret
}
break
}
else
{
if(1==grid[_x][_y])
{
tmp_x=_x
tmp_y=_y
#if 1
ret=dis+abs(_x-_i)+abs(_y-_j)-1
if(ret>max)
max=ret
#endif
break
}
}
}
}
return max
}
int main(void)
{
freopen(“snail.in”,“r”,stdin);
freopen(“snail.out”,“w”,stdout);
int i,j
char ch
int row,ans
scanf(“%d%d%c”,N,&B);
memset(grid,0,sizeof(grid));
for(i=0i<B;i++)
{
scanf(“%c”,ch);
scanf(“%d%c”,row);
grid[row][ch-‘A’+1]=2
}
for(i=0i<=N+1;i++)
grid[0][i]=grid[i][0]=2
for(i=0i<=N+1;i++)
grid[N+1][i]=grid[i][N+1]=2
#if 0
for(i=0;i
{
for(j=0;j
printf(“%d “,grid[i][j]);
printf(“\n”);
}
#endif
grid[1][1]=1
ans = work(1,1,1);
printf(“%d\n“,ans);
return 0
}

2011-03-28
USACO 5.1.3 Musical Themes

中文题目
这题我是用dp做的,首先可以把相邻两个数的差算出来,比如说给一个数列1 2 4 7 8 2 3 5 8,那么得到一个新数列:1 2 3 1 -6 1 2 3,这个新数列是上面那个数列相邻两项的差.然后我们的任务就变成了在这个新数列中求一个子序列,至少有4个元素[这里是4=5-1],然后至少重复2次,求这样的子序列的最大长度.我的做法是这样的,下面是伪代码:
for i=1 to N
for j=i+1 to N
if(j<=f[i-1][j-1]+i+1)
continue;//保证不重叠
if(num[i]==num[j])//这里是转移的一个条件
f[i][j]=f[i-1][j-1]+1;
if(f[i][j]>max)//更新最大值
max=f[i][j]
if(max<4)//这里是考虑那个最短为5个note的条件
max=-1;
max++;
printf(max)
但是这样之后在本地你可以全部AC,但是一提交你就会得到一个#9的错误,爆内存了.因为这里你必须开5000*5000的内存,可是这已经远远超过了16M了,然后你会发现f[i][j]只与f[i-1]k有关,那么我们就可以只开成这样了f[2][5006],转移的时候变成这样就OK了,f[i%2][j]=f[(i-1)%2][j-1]+1,不过这里还有一点就是每次i循环那里必须清空将要算的那一个数组,不然又值残留在那里,会导致错误,由于一开始没有考虑这一点错了一次.这样的话程序就好写了,代码量也不大,不到100行.

2011-03-27
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
}

2011-03-25
USACO 5.1.1Fencing the Cows

中文题意

凸包模板题,直接用melkman算法就OK了,melkman比其他的两种要好写[至少我这么认为],而且复杂度低.对于melkman算法就是用一个双端队列一直维护,使得在这个双端队列里面的一直是一个凸包[如果是乱序的就必须先排好序,可以就按y坐标排序如果需要再按x坐标排序,下面会有为什么要排序的一个例子].首先我们选三个点[这三个点不共线],入队列,保证队头一段时左转,队尾一端是右转.然后就把整个平面分成了下面的这样一个区域了,

首先选前三个不共线的点入队,对头保证左转弯,队尾满足右转弯,然后队的两端是同一个点,也就是加入的最后一个点.之后就把整个平面分成了如上几个区域,I,II,III,IV,V.但是排好序之后V是不可能出现的[那里为什么要排序,也是为了防止出现V这种情况],也就是说现在只可能出现其他的四个区域了,但是区域I是不行的,因为进入了凸包的内部,如果在II区域的话,那么队顶退出直至满足凸包性质为止[左转弯],III区域的话就是操作队尾,然后IV区域的话就要同时操作队顶和队尾了.这样就OK了.然后这题就是要输出凸包的周长,有了凸包,周长神马的都是浮云了~~~

2011-03-22
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
}

2011-03-18
USACO 4.4.1 Shuttle Puzzle

中文题目

这题我是用BFS过的,直接BFS,然后注意下细节就行了,一是那个移动你可以用数组记录下来,二是合法的移动一共只可能是4种:W WB _B WB然后先算前面两个再处理后面两个,这样直接BFS,最慢的是0.4s左右.但是过还是毫无压力的,过了之后一看官方的解法后,我表示压力很大**..原来还可以那么简洁,而且内存神马的也用的那么少,真的是nb啊,或许是我还太菜,又或许是我一想到BFS就没去想好一点的办法(有点自慰的感觉).官方的传在这里

▲