USACO 2.4.2 Overfencing 穿越柵欄
本文正體字版由OpenCC轉換
這道題是個簡單的Floodfill，就是從兩個不同的出口分別向迷宮中各自填充一次，然後取每個格子兩次距離出口路徑較小值集合中的最大元素輸出。
完整的程序在這裏
/*
ID: cmykrgb1
PROG: maze1
LANG: C++
*/
#include <stdio.h>
class queueelem
{
public:
queueelem()
{
up=down=left=right=0;
value=80000;
accessed=0;
};
queueelem *up,*down,*left,*right;
long value;
bool accessed;
};
class queue
{
private:
class queuelist
{
public:
queuelist(queueelem *s)
{
next=0;
point=s;
};
queueelem *point;
queuelist *next;
};
public:
long cnt;
queuelist *root,*last;
queue(queueelem *s)
{
last=root=new queuelist(s);
cnt=1;
};
void push(queueelem *s)
{
if (cnt)
{
last->next=new queuelist(s);
last=last->next;
}
else
{
last=root=new queuelist(s);
}
cnt++;
};
queueelem* pop()
{
queuelist *r;
queueelem *s;
r=root;
root=root->next;
s=r->point;
delete r;
cnt--;
return s;
};
};
FILE *fi,*fo;
char map[400][100];
queueelem mapq[101][40],mapw[101][40],ck1,ck2;
int w,h;
long M=0;
long max(long i,long j)
{
return i>j?i:j;
}
long min(long i,long j)
{
return i<j?i:j;
}
void presolve()
{
fi=fopen("maze1.in","r");
int i,j,x,y;
ck1.value=ck2.value=0;
fscanf(fi,"%d%dn",&w,&h);
for (i=1;i<=2*h+1;i++)
{
j=1;
while ((map[i][j]=getc(fi))!=10) j++;
}
for (i=1;i<=h;i++)
{
for (j=1;j<=w;j++)
{
x=i*2;y=j*2;
if (map[x-1][y]==' ')
if (i==1)
{
if (ck1.left==0)
{
mapq[i][j].up=&ck1;
ck1.left=&mapq[i][j];
}
else
{
mapq[i][j].up=&ck2;
ck2.left=&mapq[i][j];
}
}
else
mapq[i][j].up=&mapq[i-1][j];
if (map[x][y+1]==' ')
if (j==w)
{
if (ck1.left==0)
{
mapq[i][j].right=&ck1;
ck1.left=&mapq[i][j];
}
else
{
mapq[i][j].right=&ck2;
ck2.left=&mapq[i][j];
}
}
else
mapq[i][j].right=&mapq[i][j+1];
if (map[x+1][y]==' ')
if (i==h)
{
if (ck1.left==0)
{
mapq[i][j].down=&ck1;
ck1.left=&mapq[i][j];
}
else
{
mapq[i][j].down=&ck2;
ck2.left=&mapq[i][j];
}
}
else
mapq[i][j].down=&mapq[i+1][j];
if (map[x][y-1]==' ')
if (j==1)
{
if (ck1.left==0)
{
mapq[i][j].left=&ck1;
ck1.left=&mapq[i][j];
}
else
{
mapq[i][j].left=&ck2;
ck2.left=&mapq[i][j];
}
}
else
mapq[i][j].left=&mapq[i][j-1];
}
}
fclose(fi);
fi=fopen("maze1.in","r");
fscanf(fi,"%d%dn",&w,&h);
for (i=1;i<=2*h+1;i++)
{
j=1;
while ((map[i][j]=getc(fi))!=10) j++;
}
for (i=1;i<=h;i++)
{
for (j=1;j<=w;j++)
{
x=i*2;y=j*2;
if (map[x-1][y]==' ')
if (i==1)
{
if (ck1.left==0)
{
mapw[i][j].up=&ck1;
ck1.left=&mapw[i][j];
}
else
{
mapw[i][j].up=&ck2;
ck2.left=&mapw[i][j];
}
}
else
mapw[i][j].up=&mapw[i-1][j];
if (map[x][y+1]==' ')
if (j==w)
{
if (ck1.left==0)
{
mapw[i][j].right=&ck1;
ck1.left=&mapw[i][j];
}
else
{
mapw[i][j].right=&ck2;
ck2.left=&mapw[i][j];
}
}
else
mapw[i][j].right=&mapw[i][j+1];
if (map[x+1][y]==' ')
if (i==h)
{
if (ck1.left==0)
{
mapw[i][j].down=&ck1;
ck1.left=&mapw[i][j];
}
else
{
mapw[i][j].down=&ck2;
ck2.left=&mapw[i][j];
}
}
else
mapw[i][j].down=&mapw[i+1][j];
if (map[x][y-1]==' ')
if (j==1)
{
if (ck1.left==0)
{
mapw[i][j].left=&ck1;
ck1.left=&mapw[i][j];
}
else
{
mapw[i][j].left=&ck2;
ck2.left=&mapw[i][j];
}
}
else
mapw[i][j].left=&mapw[i][j-1];
}
}
fclose(fi);
}
void solve()
{
queue *Q;
queueelem *s,*p;
long t=0;
Q=new queue(&ck1);
while (Q->cnt)
{
s=Q->pop();
t=s->value+1;
if (s->left)
{
p=s->left;
if (!p->accessed)
{
if (p->value>t) p->value=t;
p->accessed=true;
Q->push(p);
}
}
if (s->right)
{
p=s->right;
if (!p->accessed)
{
if (p->value>t) p->value=t;
p->accessed=true;
Q->push(p);
}
}
if (s->up)
{
p=s->up;
if (!p->accessed)
{
if (p->value>t) p->value=t;
p->accessed=true;
Q->push(p);
}
}
if (s->down)
{
p=s->down;
if (!p->accessed)
{
if (p->value>t) p->value=t;
p->accessed=true;
Q->push(p);
}
}
}
delete Q;
Q=new queue(&ck2);
while (Q->cnt)
{
s=Q->pop();
t=s->value+1;
if (s->left)
{
p=s->left;
if (!p->accessed)
{
if (p->value>t) p->value=t;
p->accessed=true;
Q->push(p);
}
}
if (s->right)
{
p=s->right;
if (!p->accessed)
{
if (p->value>t) p->value=t;
p->accessed=true;
Q->push(p);
}
}
if (s->up)
{
p=s->up;
if (!p->accessed)
{
if (p->value>t) p->value=t;
p->accessed=true;
Q->push(p);
}
}
if (s->down)
{
p=s->down;
if (!p->accessed)
{
if (p->value>t) p->value=t;
p->accessed=true;
Q->push(p);
}
}
}
delete Q;
}
void sufsolve()
{
int i,j;
for (i=1;i<=h;i++)
{
for (j=1;j<=w;j++)
{
M=max(M,min(mapq[i][j].value,mapw[i][j].value));
}
}
fprintf(fo,"%ldn",M);
fclose(fo);
}
int main(void)
{
fo=fopen("maze1.out","w");
presolve();
solve();
sufsolve();
return 0;
}
上次修改時間 2017-02-03