USACO 2.4.2 Overfencing 穿越柵欄

這道題是個簡單的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;
}

相關日誌