分类目录归档：acm

[POJ 2079]

旋转卡壳

题意：给出最多50000个点，可取任意3点作三角形，求这些三角形中得面积最大值。

首先，可以明确的是三角形的三个顶点必定在凸包上。求出凸包后，点的数量减少到O(n^2)算法可解。

然后，需要考虑的是最大面积三角形的三点会以何种形式出现。一开始考虑的是对于所有的对踵边，枚举其对应的所有三角形，但是WA。后来发现，三角形的三边可以都不为对踵边。应该枚举的是各个点对应的最大三角形面积。在求顶点i对应的最大三角形面积时，要依次求出当j取其余n-1个点时对应的最大三角形面积，因此，可以构造如下算法：

0. 初始化顶点i为第一个顶点：
1. 初始化j为i在凸包上的下一个顶点
2. 取k为使area(i,j,k)最大的顶点，更新最大面积
3. 当j!=i时，取j为下一个顶点，回到2.；否则取i为下一个顶点，若未取尽，回到1.

其中第3步计算k时，容易利用旋转卡壳的思想证明如下结论：边(i,j+1)对应的k，必定在边(i,j)对应的k之后。由此，对于某个i，其对应的j和k的总自增次数都是O(n)级别的，总体复杂度便是O(n^2)。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define eps 1e-8
#define nt(i) (i==n?0:i)

int n;
int stk[50000],sl;
double mx;

struct E
{
    double x,y,a,r;
    bool operator < (const E &p) const
    {
        return a<p.a;
    }
}e[50001];

double crs(double x1,double y1,double x2,double y2)
{
    return x1*y2-x2*y1;
}

double area(int i,int j,int k)
{
    double x1=e[i].x,y1=e[i].y;
    double x2=e[j].x,y2=e[j].y;
    double x3=e[k].x,y3=e[k].y;
    return abs(crs(x2-x1,y2-y1,x3-x1,y3-y1))/2;
}

void init()
{
    int i,j,k,l;
    sl=0;
    mx=0;
    double xm=0,ym=0;
    double x1,y1,x2,y2,x3,y3;
    for(i=0;i<n;i++)
    {
        scanf("%lf%lf",&e[i].x,&e[i].y);
        xm+=e[i].x;
        ym+=e[i].y;
    }
    xm/=n;
    ym/=n;
    for(i=0;i<n;i++)
    {
        e[i].x-=xm;
        e[i].y-=ym;
        e[i].a=atan2(e[i].y,e[i].x);
        e[i].r=sqrt(pow(e[i].y,2)+pow(e[i].x,2));
    }
    sort(e,e+n);
    for(i=j=0;i<n;i++)
    {
        if(e[i].r>e[j].r)
            j=i;
    }
    reverse(e,e+j);
    reverse(e+j,e+n);
    reverse(e,e+n);
    e[n++]=e[0];
    stk[sl++]=0;
    stk[sl++]=1;
    for(i=2;i<n;i++)
    {
        if(sl<2)
        {
            stk[sl++]=i;
            continue;
        }
        x1=e[i].x; y1=e[i].y;
        while(sl>1)
        {
            j=stk[sl-1];
            k=stk[sl-2];
            x2=e[j].x; y2=e[j].y;
            x3=e[k].x; y3=e[k].y;
            if(crs(x2-x3,y2-y3,x1-x2,y1-y2)>eps)
                break;
            sl--;
        }
        stk[sl++]=i;
    }
    for(i=0;i<sl-1;i++)
        e[i]=e[stk[i]];
    n=sl-1;
}

void solve()
{
    int i,j,k;
    double u,v;
    for(i=0;i<n;i++)
    {
        for(j=nt(i+1),k=nt(j+1);j!=i;j=nt(j+1))
        {
            u=area(i,j,k);
            while(k!=i&&u<(v=area(i,j,nt(k+1))))
            {
                k=nt(k+1);
                u=v;
            }
            mx=max(mx,u);
        }
    }
    printf("%.2f\n",mx);
}

int main()
{
    while(~scanf("%d",&n)&&~n)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-8

#define nt(i) (i==n?0:i)

int n;

int stk[50000],sl;

double mx;

struct E

{

double x,y,a,r;

bool operator < (const E &p) const

{

return a<p.a;

}

}e[50001];

double crs(double x1,double y1,double x2,double y2)

{

return x1*y2-x2*y1;

}

double area(int i,int j,int k)

{

double x1=e[i].x,y1=e[i].y;

double x2=e[j].x,y2=e[j].y;

double x3=e[k].x,y3=e[k].y;

return abs(crs(x2-x1,y2-y1,x3-x1,y3-y1))/2;

}

void init()

{

int i,j,k,l;

sl=0;

mx=0;

double xm=0,ym=0;

double x1,y1,x2,y2,x3,y3;

for(i=0;i<n;i++)

{

scanf("%lf%lf",&e[i].x,&e[i].y);

xm+=e[i].x;

ym+=e[i].y;

}

xm/=n;

ym/=n;

for(i=0;i<n;i++)

{

e[i].x-=xm;

e[i].y-=ym;

e[i].a=atan2(e[i].y,e[i].x);

e[i].r=sqrt(pow(e[i].y,2)+pow(e[i].x,2));

}

sort(e,e+n);

for(i=j=0;i<n;i++)

{

if(e[i].r>e[j].r)

j=i;

}

reverse(e,e+j);

reverse(e+j,e+n);

reverse(e,e+n);

e[n++]=e[0];

stk[sl++]=0;

stk[sl++]=1;

for(i=2;i<n;i++)

{

if(sl<2)

{

stk[sl++]=i;

continue;

}

x1=e[i].x; y1=e[i].y;

while(sl>1)

{

j=stk[sl-1];

k=stk[sl-2];

x2=e[j].x; y2=e[j].y;

x3=e[k].x; y3=e[k].y;

if(crs(x2-x3,y2-y3,x1-x2,y1-y2)>eps)

break;

sl--;

}

stk[sl++]=i;

}

for(i=0;i<sl-1;i++)

e[i]=e[stk[i]];

n=sl-1;

}

void solve()

{

int i,j,k;

double u,v;

for(i=0;i<n;i++)

{

for(j=nt(i+1),k=nt(j+1);j!=i;j=nt(j+1))

{

u=area(i,j,k);

while(k!=i&&u<(v=area(i,j,nt(k+1))))

{

k=nt(k+1);

u=v;

}

mx=max(mx,u);

}

printf("%.2f\n",mx);

}

int main()

{

while(~scanf("%d",&n)&&~n)

{

init();

solve();

}

return 0;

}

[POJ 2540]

发表回复

Hotter Colder

半平面交

题意：在大小为10*10的矩形内有一个“最热点”，矩形内离最热点越远越冷。初始位置（0，0），移动50次，每次给出移动的目标位置以及相对之前位置的温度变化情况。对于每次移动，需要计算可能存在最热点的区域面积。

分析：初始整个矩形都是可行的，每次移动结果若是“Hotter”或者“Colder”，相当于将之前的可行区域进行了切分；若是“Same”则可行区域变为线段，面积恒为0。每次切分可以用半平面来表示。求面积时，由于题目数据量很小，依然可以O(n^3)地处理。具体做法是，求出每两条直线间的交点（包括初始矩形对应的4条边线），然后用各半平面方程判可行，得到的可行点便是可行区域的边界点。接下来，取它们的中心，再按极坐标排序，依次求中心与每两相邻点围成三角形的面积，最后求和即可。干净利落的1A解决。

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define eps 1e-8

int el,pl,tag;
char s[100];

struct E
{
    double x1,y1,xd,yd;
    double a,b,c;
}e[50];

struct P
{
    double x,y,ang;
    bool operator < (const P& p) const
    {
        return ang<p.ang;
    }
}p[2000];

void init()
{
    e[el].x1=0; e[el].y1=0; e[el].xd=0; e[el].yd=10;
    e[el].a=1; e[el].b=0; e[el].c=0;
    el++;
    e[el].x1=0; e[el].y1=10; e[el].xd=10; e[el].yd=0;
    e[el].a=0; e[el].b=1; e[el].c=-10;
    el++;
    e[el].x1=10; e[el].y1=10; e[el].xd=0; e[el].yd=-10;
    e[el].a=1; e[el].b=0; e[el].c=-10;
    el++;
    e[el].x1=10; e[el].y1=0; e[el].xd=-10; e[el].yd=0;
    e[el].a=0; e[el].b=1; e[el].c=0;
    el++;
}

double crs(double x1,double y1,double x2,double y2)
{
    return x1*y2-x2*y1;
}

void adde(double x1,double y1,double x2,double y2)
{
    double x3=(x1+x2)/2,y3=(y1+y2)/2;
    double ang=atan2(x2-x1,y1-y2);
    double x4=x3+1.0*cos(ang),y4=y3+1.0*sin(ang);
    e[el].x1=x3; e[el].y1=y3;
    e[el].xd=x4-x3; e[el].yd=y4-y3;
    e[el].a=y3-y4; e[el].b=x4-x3;
    e[el].c=(y4-y3)*x3-(x4-x3)*y3;
    if(abs(e[el].a)<eps)
    {
        e[el].a=0;
        e[el].c/=e[el].b;
        e[el].b=1;
    }
    else
    {
        e[el].b/=e[el].a;
        e[el].c/=e[el].a;
        e[el].a=1;
    }
    el++;
}

double clcd()
{
    if(tag)
        return 0;
    pl=0;
    int i,j,k,l;
    double x,y,xm=0,ym=0,d=0;
    double a1,b1,c1,a2,b2,c2;
    for(i=0;i<el-1;i++)
    {
        a1=e[i].a; b1=e[i].b; c1=e[i].c;
        for(j=i+1;j<el;j++)
        {
            a2=e[j].a; b2=e[j].b; c2=e[j].c;
            if(abs(a1-a2)<eps&&abs(b1-b2)<eps)
                continue;
            if(abs(a1)<eps)
            {
                y=-c1/b1;
                x=(-c2-b2*y)/a2;
            }
            else
            {
                y=(a2*c1-a1*c2)/(a1*b2-a2*b1);
                x=(-c1-b1*y)/a1;
            }
            p[pl].x=x;
            p[pl].y=y;
            pl++;
        }
    }
    for(i=j=0;i<pl;i++)
    {
        x=p[i].x;
        y=p[i].y;
        for(l=0;l<el;l++)
        {
            if(crs(x-e[l].x1,y-e[l].y1,e[l].xd,e[l].yd)<-eps)
                break;
        }
        if(l==el)
        {
            xm+=x;
            ym+=y;
            p[j++]=p[i];
        }
    }
    pl=j;
    xm/=pl;
    ym/=pl;
    for(i=0;i<pl;i++)
        p[i].ang=atan2(p[i].x-xm,p[i].y-ym);
    sort(p,p+pl);
    for(i=0;i<pl;i++)
    {
        j=(i+1)%pl;
        d+=abs(crs(xm-p[i].x,ym-p[i].y,xm-p[j].x,ym-p[j].y))*0.5;
    }
    return d;
}

void solve()
{
    int i,j,k,l;
    double x1=0,y1=0,x2,y2;
    while(~scanf("%lf%lf%s",&x2,&y2,s))
    {
        if(s[0]=='H')
            adde(x1,y1,x2,y2);
        else if(s[0]=='C')
            adde(x2,y2,x1,y1);
        else
            tag=1;
        x1=x2;
        y1=y2;
        printf("%.2f\n",clcd());
    }
}

int main()
{
    init();
    solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-8

int el,pl,tag;

char s[100];

struct E

{

double x1,y1,xd,yd;

double a,b,c;

}e[50];

struct P

{

double x,y,ang;

bool operator < (const P& p) const

{

return ang<p.ang;

}

}p[2000];

void init()

{

e[el].x1=0; e[el].y1=0; e[el].xd=0; e[el].yd=10;

e[el].a=1; e[el].b=0; e[el].c=0;

el++;

e[el].x1=0; e[el].y1=10; e[el].xd=10; e[el].yd=0;

e[el].a=0; e[el].b=1; e[el].c=-10;

el++;

e[el].x1=10; e[el].y1=10; e[el].xd=0; e[el].yd=-10;

e[el].a=1; e[el].b=0; e[el].c=-10;

el++;

e[el].x1=10; e[el].y1=0; e[el].xd=-10; e[el].yd=0;

e[el].a=0; e[el].b=1; e[el].c=0;

el++;

}

double crs(double x1,double y1,double x2,double y2)

{

return x1*y2-x2*y1;

}

void adde(double x1,double y1,double x2,double y2)

{

double x3=(x1+x2)/2,y3=(y1+y2)/2;

double ang=atan2(x2-x1,y1-y2);

double x4=x3+1.0*cos(ang),y4=y3+1.0*sin(ang);

e[el].x1=x3; e[el].y1=y3;

e[el].xd=x4-x3; e[el].yd=y4-y3;

e[el].a=y3-y4; e[el].b=x4-x3;

e[el].c=(y4-y3)*x3-(x4-x3)*y3;

if(abs(e[el].a)<eps)

{

e[el].a=0;

e[el].c/=e[el].b;

e[el].b=1;

}

else

{

e[el].b/=e[el].a;

e[el].c/=e[el].a;

e[el].a=1;

}

el++;

}

double clcd()

{

if(tag)

return 0;

pl=0;

int i,j,k,l;

double x,y,xm=0,ym=0,d=0;

double a1,b1,c1,a2,b2,c2;

for(i=0;i<el-1;i++)

{

a1=e[i].a; b1=e[i].b; c1=e[i].c;

for(j=i+1;j<el;j++)

{

a2=e[j].a; b2=e[j].b; c2=e[j].c;

if(abs(a1-a2)<eps&&abs(b1-b2)<eps)

continue;

if(abs(a1)<eps)

{

y=-c1/b1;

x=(-c2-b2*y)/a2;

}

else

{

y=(a2*c1-a1*c2)/(a1*b2-a2*b1);

x=(-c1-b1*y)/a1;

}

p[pl].x=x;

p[pl].y=y;

pl++;

}

for(i=j=0;i<pl;i++)

{

x=p[i].x;

y=p[i].y;

for(l=0;l<el;l++)

{

if(crs(x-e[l].x1,y-e[l].y1,e[l].xd,e[l].yd)<-eps)

break;

}

if(l==el)

{

xm+=x;

ym+=y;

p[j++]=p[i];

}

pl=j;

xm/=pl;

ym/=pl;

for(i=0;i<pl;i++)

p[i].ang=atan2(p[i].x-xm,p[i].y-ym);

sort(p,p+pl);

for(i=0;i<pl;i++)

{

j=(i+1)%pl;

d+=abs(crs(xm-p[i].x,ym-p[i].y,xm-p[j].x,ym-p[j].y))*0.5;

}

return d;

}

void solve()

{

int i,j,k,l;

double x1=0,y1=0,x2,y2;

while(~scanf("%lf%lf%s",&x2,&y2,s))

{

if(s[0]=='H')

adde(x1,y1,x2,y2);

else if(s[0]=='C')

adde(x2,y2,x1,y1);

else

tag=1;

x1=x2;

y1=y2;

printf("%.2f\n",clcd());

}

int main()

{

init();

solve();

return 0;

}

[POJ 3384]

发表回复

Feng Shui

半平面交

题意：给出一个凸多边形描述，问如何在凸多边形内放两个半径都为r的圆，使两圆覆盖区域并集的面积最大。两圆可以重叠，但重叠部分面积不累加。圆不能超出凸多边形的边界。题目保证有解，若有多解，输出任意一组。

根据题意，目标要使两圆重叠区域最小。很容易推出可行的圆心区域是原凸多边形各边向内“塌缩”r后围成的新多边形。那么，在这个新多边形内，找出距离最远的两个端点即可。

实现起来也不太难，由于数据规模不大（n最多100），直接用了O(n^3)的方法。具体做法是，首先算出各边沿斜率直角方向向内平移r后的新方程，然后求各直线间的交点。由于塌缩后，某些直线会完全位于有效区域之外，因此，对于这O(n^2)个交点，需要再用n条新直线方程判是否有效。最后，在剩余的交点中找出距离最远的两个即可。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define eps 1e-8

int n,mxi,mxj;
double r,x[10000],y[10000],mx;

struct E
{
    double x1,y1,x2,y2;
    double a,b,c;
}e[100];

void init()
{
    int i,j;
    double ang,x1,y1,x2,y2;
    mx=-1;
    for(i=0;i<n;i++)
        scanf("%lf%lf",x+i,y+i);
    for(i=0;i<n;i++)
    {
        j=(i+1)%n;
        x1=x[i]; y1=y[i]; x2=x[j]; y2=y[j];
        ang=atan2(x1-x2,y2-y1);
        x1+=r*cos(ang); y1+=r*sin(ang);
        x2+=r*cos(ang); y2+=r*sin(ang);
        e[i].x1=x1; e[i].y1=y1; e[i].x2=x2; e[i].y2=y2;
        e[i].a=y1-y2;
        e[i].b=x2-x1;
        e[i].c=(y2-y1)*x1-(x2-x1)*y1;
        if(abs(e[i].a)<eps)
        {
            e[i].a=0;
            e[i].c/=e[i].b;
            e[i].b=1;
        }
        else
        {
            e[i].b/=e[i].a;
            e[i].c/=e[i].a;
            e[i].a=1;
        }
    }
}

double crs(double x0,double y0,double x1,double y1,
        double x2,double y2)
{
    x1-=x0; y1-=y0; x2-=x0; y2-=y0;
    return x1*y2-x2*y1;
}

void solve()
{
    int i,j,k,l;
    double a1,b1,c1,a2,b2,c2,d;
    for(i=k=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            a1=e[i].a; b1=e[i].b; c1=e[i].c;
            a2=e[j].a; b2=e[j].b; c2=e[j].c;
            if(abs(a1-a2)<eps&&abs(b1-b2)<eps)
                continue;
            if(abs(a1)<eps)
            {
                y[k]=-c1/b1;
                x[k]=(-c2-b2*y[k])/a2;
            }
            else
            {
                y[k]=(a2*c1-a1*c2)/(a1*b2-a2*b1);
                x[k]=(-c1-b1*y[k])/a1;
            }
            k++;
        }
    }
    for(i=l=0;i<k;i++)
    {
        for(j=0;j<n;j++)
        {
            if(crs(e[j].x1,e[j].y1,x[i],y[i],e[j].x2,e[j].y2)<-eps)
                break;
        }
        if(j==n)
        {
            x[l]=x[i];
            y[l]=y[i];
            l++;
        }
    }
    for(i=0;i<l-1;i++)
    {
        for(j=i+1;j<l;j++)
        {
            d=pow(x[i]-x[j],2)+pow(y[i]-y[j],2);
            if(d>mx)
            {
                mx=d;
                mxi=i;
                mxj=j;
            }
        }
    }
    printf("%.4f %.4f %.4f %.4f\n",x[mxi],y[mxi],x[mxj],y[mxj]);
}

int main()
{
    while(~scanf("%d%lf",&n,&r))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-8

int n,mxi,mxj;

double r,x[10000],y[10000],mx;

struct E

{

double x1,y1,x2,y2;

double a,b,c;

}e[100];

void init()

{

int i,j;

double ang,x1,y1,x2,y2;

mx=-1;

for(i=0;i<n;i++)

scanf("%lf%lf",x+i,y+i);

for(i=0;i<n;i++)

{

j=(i+1)%n;

x1=x[i]; y1=y[i]; x2=x[j]; y2=y[j];

ang=atan2(x1-x2,y2-y1);

x1+=r*cos(ang); y1+=r*sin(ang);

x2+=r*cos(ang); y2+=r*sin(ang);

e[i].x1=x1; e[i].y1=y1; e[i].x2=x2; e[i].y2=y2;

e[i].a=y1-y2;

e[i].b=x2-x1;

e[i].c=(y2-y1)*x1-(x2-x1)*y1;

if(abs(e[i].a)<eps)

{

e[i].a=0;

e[i].c/=e[i].b;

e[i].b=1;

}

else

{

e[i].b/=e[i].a;

e[i].c/=e[i].a;

e[i].a=1;

}

double crs(double x0,double y0,double x1,double y1,

double x2,double y2)

{

x1-=x0; y1-=y0; x2-=x0; y2-=y0;

return x1*y2-x2*y1;

}

void solve()

{

int i,j,k,l;

double a1,b1,c1,a2,b2,c2,d;

for(i=k=0;i<n-1;i++)

{

for(j=i+1;j<n;j++)

{

a1=e[i].a; b1=e[i].b; c1=e[i].c;

a2=e[j].a; b2=e[j].b; c2=e[j].c;

if(abs(a1-a2)<eps&&abs(b1-b2)<eps)

continue;

if(abs(a1)<eps)

{

y[k]=-c1/b1;

x[k]=(-c2-b2*y[k])/a2;

}

else

{

y[k]=(a2*c1-a1*c2)/(a1*b2-a2*b1);

x[k]=(-c1-b1*y[k])/a1;

}

k++;

}

for(i=l=0;i<k;i++)

{

for(j=0;j<n;j++)

{

if(crs(e[j].x1,e[j].y1,x[i],y[i],e[j].x2,e[j].y2)<-eps)

break;

}

if(j==n)

{

x[l]=x[i];

y[l]=y[i];

l++;

}

for(i=0;i<l-1;i++)

{

for(j=i+1;j<l;j++)

{

d=pow(x[i]-x[j],2)+pow(y[i]-y[j],2);

if(d>mx)

{

mx=d;

mxi=i;

mxj=j;

}

printf("%.4f %.4f %.4f %.4f\n",x[mxi],y[mxi],x[mxj],y[mxj]);

}

int main()

{

while(~scanf("%d%lf",&n,&r))

{

init();

solve();

}

return 0;

}

[POJ 3317]

发表回复

Stake Your Claim

博弈树搜索

题意：棋类游戏盘面大小最多8*8，两方轮流在空格落子，最后计算双方各自的最大4连通区域的大小来判胜负。空格最多10个。

题目数据范围很小，考虑到深度最多为10，一开始直接写了个O(n!)的算法，TLE。然后想明白可以用Alpha-Beta剪枝，还是TLE。最后发现空格最多10个，用位相量不过是4^10个状态，可以剔除重复状态的计算，然后就开始WA了。

持续的不解后……看了看讨论，才发现原来大家的思路都是一样的（卡了哪题都能看到ZaakDov…）。WA的原因正是Alpha-Beta剪枝导致子状态无法达到最优值，从而记录下了错误的状态值。正解是直接记忆化搜索即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,x,y,el,b[8][8],bi;
int mv[4][2]={-1,0, 1,0, 0,-1, 0,1};
char s[8][9];
int q[64][2],qh,qt;
char d[1<<20];

struct E
{
    int x,y,b;
}e[10];

bool chk(int i,int j,int k)
{
    return i>-1&&i<n&&j>-1&&j<n&&b[i][j]!=bi&&s[i][j]==k;
}

int calc()
{
    int i,j;
    for(i=j=0;i<el;i++)
        j=(j<<2)+s[e[i].x][e[i].y];
    return j;
}

int bfs(int i,int j)
{
    int k=s[i][j],l=0,ml,mi,mj;
    b[i][j]=bi;
    qh=qt=0;
    q[qt][0]=i;
    q[qt][1]=j;
    qt++;
    while(qh<qt)
    {
        i=q[qh][0];
        j=q[qh][1];
        qh++;
        l++;
        for(ml=0;ml<4;ml++)
        {
            mi=i+mv[ml][0];
            mj=j+mv[ml][1];
            if(chk(mi,mj,k))
            {
                b[mi][mj]=bi;
                q[qt][0]=mi;
                q[qt][1]=mj;
                qt++;
            }
        }
    }
    return l;
}

int dfs(int ei,int p)
{
    int h,i,j,k,l;
    h=calc();
    if(d[h]!=127)
        return d[h];
    if(ei==el)
    {
        bi++;
        for(i=k=l=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(b[i][j]!=bi)
                {
                    if(s[i][j]==p)
                        k=max(k,bfs(i,j));
                    else
                        l=max(l,bfs(i,j));
                }
            }
        }
        return k-l;
    }
    for(i=0,j=-100;i<el;i++)
    {
        if(!e[i].b)
        {
            s[e[i].x][e[i].y]=p;
            e[i].b=1;
            k=dfs(ei+1,p^1);
            e[i].b=0;
            if(-k>j)
            {
                j=-k;
                if(!ei)
                {
                    x=e[i].x;
                    y=e[i].y;
                }
            }
            s[e[i].x][e[i].y]=2;
        }
    }
    return d[h]=j;
}

void solve()
{
    int i,j,k,l;
    el=bi=0;
    memset(b,0,sizeof b);
    memset(d,127,sizeof d);
    for(i=k=l=0;i<n;i++)
    {
        scanf("%s",s[i]);
        for(j=0;j<n;j++)
        {
            if(s[i][j]=='0')
            {
                k++;
                s[i][j]=0;
            }
            else if(s[i][j]=='1')
            {
                l++;
                s[i][j]=1;
            }
            else
            {
                e[el].x=i;
                e[el].y=j;
                e[el].b=0;
                el++;
                s[i][j]=2;
            }
        }
    }
    k=dfs(0,k==l?0:1);
    printf("(%d,%d) %d\n",x,y,k);
}

int main()
{
    while(~scanf("%d",&n)&&n)
        solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,x,y,el,b[8][8],bi;

int mv[4][2]={-1,0, 1,0, 0,-1, 0,1};

char s[8][9];

int q[64][2],qh,qt;

char d[1<<20];

struct E

{

int x,y,b;

}e[10];

bool chk(int i,int j,int k)

{

return i>-1&&i<n&&j>-1&&j<n&&b[i][j]!=bi&&s[i][j]==k;

}

int calc()

{

int i,j;

for(i=j=0;i<el;i++)

j=(j<<2)+s[e[i].x][e[i].y];

return j;

}

int bfs(int i,int j)

{

int k=s[i][j],l=0,ml,mi,mj;

b[i][j]=bi;

qh=qt=0;

q[qt][0]=i;

q[qt][1]=j;

qt++;

while(qh<qt)

{

i=q[qh][0];

j=q[qh][1];

qh++;

l++;

for(ml=0;ml<4;ml++)

{

mi=i+mv[ml][0];

mj=j+mv[ml][1];

if(chk(mi,mj,k))

{

b[mi][mj]=bi;

q[qt][0]=mi;

q[qt][1]=mj;

qt++;

}

return l;

}

int dfs(int ei,int p)

{

int h,i,j,k,l;

h=calc();

if(d[h]!=127)

return d[h];

if(ei==el)

{

bi++;

for(i=k=l=0;i<n;i++)

{

for(j=0;j<n;j++)

{

if(b[i][j]!=bi)

{

if(s[i][j]==p)

k=max(k,bfs(i,j));

else

l=max(l,bfs(i,j));

}

return k-l;

}

for(i=0,j=-100;i<el;i++)

{

if(!e[i].b)

{

s[e[i].x][e[i].y]=p;

e[i].b=1;

k=dfs(ei+1,p^1);

e[i].b=0;

if(-k>j)

{

j=-k;

if(!ei)

{

x=e[i].x;

y=e[i].y;

}

s[e[i].x][e[i].y]=2;

}

return d[h]=j;

}

void solve()

{

int i,j,k,l;

el=bi=0;

memset(b,0,sizeof b);

memset(d,127,sizeof d);

for(i=k=l=0;i<n;i++)

{

scanf("%s",s[i]);

for(j=0;j<n;j++)

{

if(s[i][j]=='0')

{

k++;

s[i][j]=0;

}

else if(s[i][j]=='1')

{

l++;

s[i][j]=1;

}

else

{

e[el].x=i;

e[el].y=j;

e[el].b=0;

el++;

s[i][j]=2;

}

k=dfs(0,k==l?0:1);

printf("(%d,%d) %d\n",x,y,k);

}

int main()

{

while(~scanf("%d",&n)&&n)

solve();

return 0;

}

[POJ 3133]

发表回复

Manhattan Wiring

插头DP

题意：给出一个最多9*9的格盘描述，其中有两个2和两个3，求将两个2和3分别用不相交的线段相连所需的最短线长。线不能交叉且仅能经过空格。

明确是插头DP后，首先要考虑如何表示状态。这题特殊之处在于线段有两条，且需要和指定的端点相连。那么，最关键的是确定如何表达有效的终状态。

考虑以下解方案：用0表示空插头，2和3分别有相应插头。那么这里每个位置需要2bit，总共是2*10=20bit。再用最低的4个bit分别表示4个端点是否有连接，由此便能用一个int来表示轮廓线状态u。判断终状态时，直接用u==15即可。其正确性在于，题目所求的是最短线长，那么若4个端点已连，且当前没有空线头，则端点间必定已存在连线。同时也可能存在不与任何端点相连的线环，但线环仅仅是增加了总线长，不影响正确性。

实现方面，由于状态数为1<<24，若直接存下各个状态的最短线长，只能用char数组，由于题目数据范围不大，这是可行的。但一开始还是用了int数组和hash处理（u%10007)。按理说直接访问状态应该要比hash快，但事实上后者比前者要快两倍多（500ms VS 1600MS）。猜测是由于hash过后状态值较为接近，内存访问要更为集中。虽然再加一些状态剪枝应该可以更快……但当前的代码长度竟已超过了5K，实在是不太明白那些2K左右跑出300ms的代码是怎么写的…… =(

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define M 1<<24
#define MS 1<<20

int n,m,ans;
int x2s,y2s,x2e,y2e,x3s,y3s,x3e,y3e;
int mem3[MS],mem4[MS];
int *st1,*st2,s1l,s2l;
int b[9][9];
char mem1[M],mem2[M],*u1,*u2,ms[M],msij;

int chk(int i,int j)
{
    return i==n||j==m||b[i][j]==1;
}

bool chs(int i,int j,int &u,int v)
{
    if(b[i][j]==v)
    {
        if(i==x2s&&j==y2s&&!(u&8))
        {
            u|=8;
            return 1;
        }
        if(i==x2e&&j==y2e&&!(u&4))
        {
            u|=4;
            return 1;
        }
        if(i==x3s&&j==y3s&&!(u&2))
        {
            u|=2;
            return 1;
        }
        if(i==x3e&&j==y3e&&!(u&1))
        {
            u|=1;
            return 1;
        }
    }
    return 0;
}

void adde(int u,int ud)
{
    if(u==15)
    {
        ans=min(ans,ud);
        return;
    }
    else if(ud>=ans)
        return;
    if(ms[u]!=msij)
    {
        ms[u]=msij;
        u2[u]=ud;
        st2[s2l++]=u;
    }
    else
        u2[u]=min(u2[u],(char)ud);
}

void init()
{
    int i,j,k,l;
    ans=0x7fffffff;
    x2s=y2s=x2e=y2e=x3s=y3s=x3e=y3e=-1;
    u1=mem1,u2=mem2;
    st1=mem3,st2=mem4,s1l=s2l=0;
    memset(ms,-1,sizeof ms);
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            scanf("%d",&b[i][j]);
            if(b[i][j]==2)
            {
                if(x2s==-1)
                    x2s=i,y2s=j;
                else if(x2e==-1)
                    x2e=i,y2e=j;
                else
                    ans=-1;
            }
            else if(b[i][j]==3)
            {
                if(x3s==-1)
                    x3s=i,y3s=j;
                else if(x3e==-1)
                    x3e=i,y3e=j;
                else
                    ans=-1;
            }
        }
    }
}

int gt(int u,int l)
{
    return (u>>(4+2*(m-l)))&3;
}

void st(int &u,int l,int v)
{
    u&=~(3<<(4+2*(m-l)));
    u|=v<<(4+2*(m-l));
}

void solve()
{
    if(ans==-1)
    {
        puts("0");
        return;
    }
    int i,j,k,l;
    int v1,v2,u,uu,ud;
    u1[0]=0;
    st1[s1l++]=0;
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            msij=i*m+j;
            if(b[i][j]==1)
                continue;
            k=chk(i+1,j)*2+chk(i,j+1);
            while(s1l)
            {
                u=st1[--s1l];
                ud=u1[u];
                v1=gt(u,m);
                v2=gt(u,j);
                if(!v1&&!v2)
                {
                    if(b[i][j]==0)
                    {
                        adde(u,ud);
                        if(k==0)
                        {
                            uu=u;
                            st(uu,j,2);
                            st(uu,m,2);
                            adde(uu,ud+1);
                            uu=u;
                            st(uu,j,3);
                            st(uu,m,3);
                            adde(uu,ud+1);
                        }
                    }
                    else if(b[i][j]>1)
                    {
                        uu=u;
                        if((k==0||k==1)&&chs(i,j,uu,b[i][j]))
                        {
                            st(uu,j,b[i][j]);
                            st(uu,m,0);
                            adde(uu,ud);
                        }
                        uu=u;
                        if((k==0||k==2)&&chs(i,j,uu,b[i][j]))
                        {
                            st(uu,j,0);
                            st(uu,m,b[i][j]);
                            adde(uu,ud);
                        }
                    }
                }
                else if(!v1||!v2)
                {
                    if(b[i][j]>1)
                    {
                        uu=u;
                        if(chs(i,j,uu,v1+v2))
                        {
                            st(uu,j,0);
                            st(uu,m,0);
                            adde(uu,ud);
                        }
                    }
                    else if(b[i][j]==0)
                    {
                        if(k==0||k==1)
                        {
                            uu=u;
                            st(uu,j,v1+v2);
                            st(uu,m,0);
                            adde(uu,ud+1);
                        }
                        if(k==0||k==2)
                        {
                            uu=u;
                            st(uu,j,0);
                            st(uu,m,v1+v2);
                            adde(uu,ud+1);
                        }
                    }
                }
                else if(v1==v2)
                {
                    if(b[i][j]==0)
                    {
                        uu=u;
                        st(uu,j,0);
                        st(uu,m,0);
                        adde(uu,ud+1);
                    }
                }
            }
            swap(u1,u2);
            swap(st1,st2);
            s1l=s2l;
            s2l=0;
        }
    }
    printf("%d\n",ans==0x7fffffff?0:ans+2);
}

int main()
{
    while(~scanf("%d%d",&n,&m)&&n)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define M 1<<24

#define MS 1<<20

int n,m,ans;

int x2s,y2s,x2e,y2e,x3s,y3s,x3e,y3e;

int mem3[MS],mem4[MS];

int *st1,*st2,s1l,s2l;

int b[9][9];

char mem1[M],mem2[M],*u1,*u2,ms[M],msij;

int chk(int i,int j)

{

return i==n||j==m||b[i][j]==1;

}

bool chs(int i,int j,int &u,int v)

{

if(b[i][j]==v)

{

if(i==x2s&&j==y2s&&!(u&8))

{

u|=8;

return 1;

}

if(i==x2e&&j==y2e&&!(u&4))

{

u|=4;

return 1;

}

if(i==x3s&&j==y3s&&!(u&2))

{

u|=2;

return 1;

}

if(i==x3e&&j==y3e&&!(u&1))

{

u|=1;

return 1;

}

return 0;

}

void adde(int u,int ud)

{

if(u==15)

{

ans=min(ans,ud);

return;

}

else if(ud>=ans)

return;

if(ms[u]!=msij)

{

ms[u]=msij;

u2[u]=ud;

st2[s2l++]=u;

}

else

u2[u]=min(u2[u],(char)ud);

}

void init()

{

int i,j,k,l;

ans=0x7fffffff;

x2s=y2s=x2e=y2e=x3s=y3s=x3e=y3e=-1;

u1=mem1,u2=mem2;

st1=mem3,st2=mem4,s1l=s2l=0;

memset(ms,-1,sizeof ms);

for(i=0;i<n;i++)

{

for(j=0;j<m;j++)

{

scanf("%d",&b[i][j]);

if(b[i][j]==2)

{

if(x2s==-1)

x2s=i,y2s=j;

else if(x2e==-1)

x2e=i,y2e=j;

else

ans=-1;

}

else if(b[i][j]==3)

{

if(x3s==-1)

x3s=i,y3s=j;

else if(x3e==-1)

x3e=i,y3e=j;

else

ans=-1;

}

int gt(int u,int l)

{

return (u>>(4+2*(m-l)))&3;

}

void st(int &u,int l,int v)

{

u&=~(3<<(4+2*(m-l)));

u|=v<<(4+2*(m-l));

}

void solve()

{

if(ans==-1)

{

puts("0");

return;

}

int i,j,k,l;

int v1,v2,u,uu,ud;

u1[0]=0;

st1[s1l++]=0;

for(i=0;i<n;i++)

{

for(j=0;j<m;j++)

{

msij=i*m+j;

if(b[i][j]==1)

continue;

k=chk(i+1,j)*2+chk(i,j+1);

while(s1l)

{

u=st1[--s1l];

ud=u1[u];

v1=gt(u,m);

v2=gt(u,j);

if(!v1&&!v2)

{

if(b[i][j]==0)

{

adde(u,ud);

if(k==0)

{

uu=u;

st(uu,j,2);

st(uu,m,2);

adde(uu,ud+1);

uu=u;

st(uu,j,3);

st(uu,m,3);

adde(uu,ud+1);

}

else if(b[i][j]>1)

{

uu=u;

if((k==0||k==1)&&chs(i,j,uu,b[i][j]))

{

st(uu,j,b[i][j]);

st(uu,m,0);

adde(uu,ud);

}

uu=u;

if((k==0||k==2)&&chs(i,j,uu,b[i][j]))

{

st(uu,j,0);

st(uu,m,b[i][j]);

adde(uu,ud);

}

else if(!v1||!v2)

{

if(b[i][j]>1)

{

uu=u;

if(chs(i,j,uu,v1+v2))

{

st(uu,j,0);

st(uu,m,0);

adde(uu,ud);

}

else if(b[i][j]==0)

{

if(k==0||k==1)

{

uu=u;

st(uu,j,v1+v2);

st(uu,m,0);

adde(uu,ud+1);

}

if(k==0||k==2)

{

uu=u;

st(uu,j,0);

st(uu,m,v1+v2);

adde(uu,ud+1);

}

else if(v1==v2)

{

if(b[i][j]==0)

{

uu=u;

st(uu,j,0);

st(uu,m,0);

adde(uu,ud+1);

}

swap(u1,u2);

swap(st1,st2);

s1l=s2l;

s2l=0;

}

printf("%d\n",ans==0x7fffffff?0:ans+2);

}

int main()

{

while(~scanf("%d%d",&n,&m)&&n)

{

init();

solve();

}

return 0;

}

[Ural 1519]

发表回复

Formula 1

插头DP

题意：给出一个最多12*12的地形描述，问有多少方式在其上建一条F1赛道。一条F1赛道为仅横竖相连且覆盖所有空地的一个环。

参考了陈丹琦的《基于连通性状态压缩的动态规划问题》，插头+轮廓线扫描。虽然论文已经给出了基本思路，但仍存在一些特殊情况，如：

0   1   2   3   4   5   6   7
* ( (   (   )   (   )   )   )

1 2	0 1 2 3 4 5 6 7 * ( ( ( ) ( ) ) )

应转变为

0   1   2   3   4   5   6   7
*   * * (   )   (   )   (   )

1 2	0 1 2 3 4 5 6 7 * * * ( ) ( ) ( )

我用了很长时间才发现这一点。

实现方面，一开始打算全部用位运算，但发现存储的时候状态数太多，无法直接开大数组存，于是又转成3进制。每次更新下一个格点的状态值时，交换内存指针，根据相应内存位置标记来判断是否置0，这样就避免了每次对大数组进行memset。另外，使用了栈来非重复地保存各状态（仅当计数值为0时入栈），避免了每次扫描整个计数数组。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define M 1594323

ll n,m,ei,ej,pn,ans;
ll mem1[M],mem2[M],mem3[M],mem4[M];
ll *mp1,*mp2,*st1,*st2,sl1,sl2;
char s[12][13],ms[M],msij;

void init()
{
    ll i,j;
    ei=ej=-1;
    ans=0;
    sl1=0;
    memset(ms,-1,sizeof ms);
    mp1=mem1;
    mp2=mem2;
    st1=mem3;
    st2=mem4;
    for(i=pn=0;i<n;i++)
    {
        scanf("%s",s[i]);
        for(j=0;j<m;j++)
        {
            if(s[i][j]=='.')
            {
                pn++;
                ei=i;
                ej=j;
            }
        }
    }
}

ll enc(ll u)
{
    ll i,l;
    for(i=l=0;l<=m;l++)
    {
        i=i*3+(u&3);
        u>>=2;
    }
    return i;
}

ll dec(ll i)
{
    ll u,l;
    for(u=l=0;l<=m;l++)
    {
        u=(u<<2)+i%3;
        i/=3;
    }
    return u;
}

ll chk(ll i,ll j)
{
    if(i==n||j==m||s[i][j]!='.')
        return 1;
    return 0;
}

ll gt(ll u,ll j)
{
    return (u>>(2*(m-j)))&3;
}

void st(ll &u,ll j,ll v)
{
    u&=~(3LL<<(2*(m-j)));
    u|=v<<(2*(m-j));
}

void ins(ll u,ll ud)
{
    ll ml=enc(u);
    if(ms[ml]!=msij)
    {
        mp2[ml]=0;
        ms[ml]=msij;
    }
    if(!mp2[ml])
        st2[sl2++]=ml;
    mp2[ml]+=ud;
}

void solve()
{
    if(ei==-1||(pn&1))
    {
        puts("0");
        return;
    }
    ll i,j,k,l,ul,cnt;
    ll u,ud,v1,v2;
    ll ms=1,ml;
    for(l=0;l<=m;l++)
        ms*=3;
    mp1[enc(0)]=1;
    st1[sl1++]=enc(0);
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            msij=i*m+j;
            if(s[i][j]=='*')
                continue;
            k=(chk(i+1,j)<<1)+(chk(i,j+1));
            sl2=0;
            while(sl1)
            {
                ml=st1[--sl1];
                u=dec(ml);
                ud=mp1[ml];
                v1=gt(u,m);
                v2=gt(u,j);
                if(!v1&&!v2)
                {
                    if(k==0)
                    {
                        st(u,j,1);
                        st(u,m,2);
                        ins(u,ud);
                    }
                }
                else if(!v1||!v2)
                {
                    if(k==0||k==1)
                    {
                        st(u,j,v1+v2);
                        st(u,m,0);
                        ins(u,ud);
                    }
                    if(k==0||k==2)
                    {
                        st(u,j,0);
                        st(u,m,v1+v2);
                        ins(u,ud);
                    }
                }
                else if(v1!=v2)
                {
                    if(v1==1&&v2==2&&(i!=ei||j!=ej))
                        continue;
                    if(v1==1&&v2==2&&i==ei&&j==ej)
                        ans+=ud;
                    st(u,j,0);
                    st(u,m,0);
                    ins(u,ud);
                }
                else if(v1==1)
                {
                    st(u,j,0);
                    st(u,m,0);
                    for(l=j+1,cnt=0;l<m;l++)
                    {
                        ul=gt(u,l);
                        if(ul==1)
                            cnt++;
                        else if(ul==2)
                        {
                            if(!cnt)
                                break;
                            cnt--;
                        }
                    }
                    st(u,l,1);
                    ins(u,ud);
                }
                else
                {
                    st(u,j,0);
                    st(u,m,0);
                    for(l=j-1,cnt=0;l>-1;l--)
                    {
                        ul=gt(u,l);
                        if(ul==2)
                            cnt++;
                        else if(ul==1)
                        {
                            if(!cnt)
                                break;
                            cnt--;
                        }
                    }
                    st(u,l,2);
                    ins(u,ud);
                }
            }
            swap(mp1,mp2);
            swap(st1,st2);
            sl1=sl2;
        }
    }
    printf("%lld\n",ans);
}

int main()
{
    while(~scanf("%lld%lld",&n,&m))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define M 1594323

ll n,m,ei,ej,pn,ans;

ll mem1[M],mem2[M],mem3[M],mem4[M];

ll *mp1,*mp2,*st1,*st2,sl1,sl2;

char s[12][13],ms[M],msij;

void init()

{

ll i,j;

ei=ej=-1;

ans=0;

sl1=0;

memset(ms,-1,sizeof ms);

mp1=mem1;

mp2=mem2;

st1=mem3;

st2=mem4;

for(i=pn=0;i<n;i++)

{

scanf("%s",s[i]);

for(j=0;j<m;j++)

{

if(s[i][j]=='.')

{

pn++;

ei=i;

ej=j;

}

ll enc(ll u)

{

ll i,l;

for(i=l=0;l<=m;l++)

{

i=i*3+(u&3);

u>>=2;

}

return i;

}

ll dec(ll i)

{

ll u,l;

for(u=l=0;l<=m;l++)

{

u=(u<<2)+i%3;

i/=3;

}

return u;

}

ll chk(ll i,ll j)

{

if(i==n||j==m||s[i][j]!='.')

return 1;

return 0;

}

ll gt(ll u,ll j)

{

return (u>>(2*(m-j)))&3;

}

void st(ll &u,ll j,ll v)

{

u&=~(3LL<<(2*(m-j)));

u|=v<<(2*(m-j));

}

void ins(ll u,ll ud)

{

ll ml=enc(u);

if(ms[ml]!=msij)

{

mp2[ml]=0;

ms[ml]=msij;

}

if(!mp2[ml])

st2[sl2++]=ml;

mp2[ml]+=ud;

}

void solve()

{

if(ei==-1||(pn&1))

{

puts("0");

return;

}

ll i,j,k,l,ul,cnt;

ll u,ud,v1,v2;

ll ms=1,ml;

for(l=0;l<=m;l++)

ms*=3;

mp1[enc(0)]=1;

st1[sl1++]=enc(0);

for(i=0;i<n;i++)

{

for(j=0;j<m;j++)

{

msij=i*m+j;

if(s[i][j]=='*')

continue;

k=(chk(i+1,j)<<1)+(chk(i,j+1));

sl2=0;

while(sl1)

{

ml=st1[--sl1];

u=dec(ml);

ud=mp1[ml];

v1=gt(u,m);

v2=gt(u,j);

if(!v1&&!v2)

{

if(k==0)

{

st(u,j,1);

st(u,m,2);

ins(u,ud);

}

else if(!v1||!v2)

{

if(k==0||k==1)

{

st(u,j,v1+v2);

st(u,m,0);

ins(u,ud);

}

if(k==0||k==2)

{

st(u,j,0);

st(u,m,v1+v2);

ins(u,ud);

}

else if(v1!=v2)

{

if(v1==1&&v2==2&&(i!=ei||j!=ej))

continue;

if(v1==1&&v2==2&&i==ei&&j==ej)

ans+=ud;

st(u,j,0);

st(u,m,0);

ins(u,ud);

}

else if(v1==1)

{

st(u,j,0);

st(u,m,0);

for(l=j+1,cnt=0;l<m;l++)

{

ul=gt(u,l);

if(ul==1)

cnt++;

else if(ul==2)

{

if(!cnt)

break;

cnt--;

}

st(u,l,1);

ins(u,ud);

}

else

{

st(u,j,0);

st(u,m,0);

for(l=j-1,cnt=0;l>-1;l--)

{

ul=gt(u,l);

if(ul==2)

cnt++;

else if(ul==1)

{

if(!cnt)

break;

cnt--;

}

st(u,l,2);

ins(u,ud);

}

swap(mp1,mp2);

swap(st1,st2);

sl1=sl2;

}

printf("%lld\n",ans);

}

int main()

{

while(~scanf("%lld%lld",&n,&m))

{

init();

solve();

}

return 0;

}

在ural上用VS 2010只能跑出0.6S左右的时间。瓶颈应该是慢在位向量和3进制间转换上面，但也没有想到太好的优化了……

ps：小小感慨一下，连这种问题都可以DP，实在是不可思议。

[POJ 3131]

发表回复

Cubic Eight-Puzzle

双向广搜

题意：有9个格子，其中8个格子有立方体。立方体相对的两面颜色相同，分别为红、白、蓝色。若某立方体相邻格为空，则该立方体可以向该方向滚动。给定初始状态，问最少滚动多少次（不大于30），可以使各盘格为指定的颜色。

类似这种搜索题，最关键的还是状态的表达。立方体的姿态可以由顶面和正面的颜色来确定，共有6种。有9个格子，考虑使用每个格子3bit，那么搜索空间的规模就是2^(3*9)，大概是1亿。接下来，考虑如何判重。如果使用一个位来表示一个状态，总共需要的内存大小为2^24bytes，也就16MB，是可行的。直接开一个char c[1<<24]，连hash都省了。由此，可以保证所有的操作全部为位运算。接下来考虑搜索的形式，一般来说双向广搜，两边的深度限制相同时可以最大化降低复杂度，但该题反向搜索时起始状态较多（256个状态），层数不深时规模已经很大。因此，正向搜索深度设为20，反向为10。正向搜索完后如果找到解，则直接输出，否则才执行反向搜索。

#include<cstdio>
#include<cstring>

#define M 500000
#define D 20

int eh,el,x,y,b,bm=0x06db6db6,xe,ye,be,ans;
int mv[4][2]={-1,0,1,0,0,-1,0,1},t[128];
int mu[8][4]={0,0,0,0, 0,0,0,0, 7,7,5,5, 4,4,6,6, 
    3,3,7,7, 6,6,2,2, 5,5,3,3, 2,2,4,4};
char s[2],c[1<<24],cr[1<<24];

struct E
{
    int x,y,b,d;
}e[M];

inline int getl(int x,int y)
{
    return ((3-y)<<3)+(3-y)+((3-x)<<1)+(3-x);
}

void init()
{
    int i,j,k,l;
    eh=el=b=be=0;
    ans=0x7fffffff;
    memset(c,0,sizeof c);
    memset(cr,0,sizeof cr);
    for(i=l=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            b=(b<<3)+5;
            scanf("%s",s);
            be=(be<<3)+t[s[0]];
            if(s[0]=='E')
            {
                xe=j+1;
                ye=i+1;
            }
        }
    }
    b&=~(7<<getl(x,y));
}

inline bool chk(int x,int y,int b,char c[])
{
    return x>0&&x<4&&y>0&&y<4&&!(c[b>>3]&(1<<(b&7)));
}

inline int calc(int bz,int xz,int yz,int x,int y,int l)
{
    int i,j,k,l1,l2;
    l1=getl(xz,yz); l2=getl(x,y);
    k=mu[(bz&(7<<l2))>>l2][l];
    bz=(bz&~(7<<l2))+(k<<l1);
    return bz;
}

void bfs()
{
    int i,j,k,l;
    e[el].x=x;
    e[el].y=y;
    e[el].b=b;
    e[el].d=0;
    c[e[el].b>>3]|=(1<<(e[el].b&7));
    el++;
    while(eh!=el)
    {
        i=eh++;
        if(e[i].d==D)
            continue;
        for(l=0;l<4;l++)
        {
            e[el].x=e[i].x+mv[l][0];
            e[el].y=e[i].y+mv[l][1];
            e[el].b=calc(e[i].b,e[i].x,e[i].y,
                    e[el].x,e[el].y,l);
            e[el].d=e[i].d+1;
            if(chk(e[el].x,e[el].y,e[el].b,c))
            {
                c[e[el].b>>3]|=(1<<(e[el].b&7));
                if((e[el].b&bm)==be)
                {
                    ans=e[el].d;
                    return;
                }
                el++;
            }
        }
    }
}

void rbfs()
{
    int i,j,k,l;
    l=1<<(getl(xe,ye)/3);
    eh=el=0;
    for(i=0;i<512;i++)
    {
        if(i&l)
            continue;
        e[el].x=xe;
        e[el].y=ye;
        e[el].b=be;
        e[el].d=0;
        for(j=i,k=0;j;j>>=1,k+=3)
        {
            e[el].b+=(j&1)<<k;
        }
        cr[e[el].b>>3]|=(1<<(e[el].b&7));
        el++;
    }
    while(eh!=el)
    {
        i=eh++;
        if(e[i].d==30-D)
            continue;
        for(l=0;l<4;l++)
        {
            e[el].x=e[i].x+mv[l][0];
            e[el].y=e[i].y+mv[l][1];
            e[el].b=calc(e[i].b,e[i].x,e[i].y,
                    e[el].x,e[el].y,l);
            e[el].d=e[i].d+1;
            if(chk(e[el].x,e[el].y,e[el].b,cr))
            {
                cr[e[el].b>>3]|=(1<<(e[el].b&7));
                if(!chk(e[el].x,e[el].y,e[el].b,c))
                {
                    ans=e[el].d+D;
                    return;
                }
                el++;
            }
        }
    }
}

void solve()
{
    if((b&bm)==be)
    {
        puts("0");
        return;
    }
    bfs();
    if(ans<0x7fffffff)
    {
        printf("%d\n",ans);
        return;
    }
    rbfs();
    printf("%d\n",ans==0x7fffffff?-1:ans);
}

int main()
{
    t['R']=2; t['W']=4; t['B']=6;
    while(~scanf("%d%d",&x,&y)&&x)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

#include<cstdio>

#include<cstring>

#define M 500000

#define D 20

int eh,el,x,y,b,bm=0x06db6db6,xe,ye,be,ans;

int mv[4][2]={-1,0,1,0,0,-1,0,1},t[128];

int mu[8][4]={0,0,0,0, 0,0,0,0, 7,7,5,5, 4,4,6,6,

3,3,7,7, 6,6,2,2, 5,5,3,3, 2,2,4,4};

char s[2],c[1<<24],cr[1<<24];

struct E

{

int x,y,b,d;

}e[M];

inline int getl(int x,int y)

{

return ((3-y)<<3)+(3-y)+((3-x)<<1)+(3-x);

}

void init()

{

int i,j,k,l;

eh=el=b=be=0;

ans=0x7fffffff;

memset(c,0,sizeof c);

memset(cr,0,sizeof cr);

for(i=l=0;i<3;i++)

{

for(j=0;j<3;j++)

{

b=(b<<3)+5;

scanf("%s",s);

be=(be<<3)+t[s[0]];

if(s[0]=='E')

{

xe=j+1;

ye=i+1;

}

b&=~(7<<getl(x,y));

}

inline bool chk(int x,int y,int b,char c[])

{

return x>0&&x<4&&y>0&&y<4&&!(c[b>>3]&(1<<(b&7)));

}

inline int calc(int bz,int xz,int yz,int x,int y,int l)

{

int i,j,k,l1,l2;

l1=getl(xz,yz); l2=getl(x,y);

k=mu[(bz&(7<<l2))>>l2][l];

bz=(bz&~(7<<l2))+(k<<l1);

return bz;

}

void bfs()

{

int i,j,k,l;

e[el].x=x;

e[el].y=y;

e[el].b=b;

e[el].d=0;

c[e[el].b>>3]|=(1<<(e[el].b&7));

el++;

while(eh!=el)

{

i=eh++;

if(e[i].d==D)

continue;

for(l=0;l<4;l++)

{

e[el].x=e[i].x+mv[l][0];

e[el].y=e[i].y+mv[l][1];

e[el].b=calc(e[i].b,e[i].x,e[i].y,

e[el].x,e[el].y,l);

e[el].d=e[i].d+1;

if(chk(e[el].x,e[el].y,e[el].b,c))

{

c[e[el].b>>3]|=(1<<(e[el].b&7));

if((e[el].b&bm)==be)

{

ans=e[el].d;

return;

}

el++;

}

void rbfs()

{

int i,j,k,l;

l=1<<(getl(xe,ye)/3);

eh=el=0;

for(i=0;i<512;i++)

{

if(i&l)

continue;

e[el].x=xe;

e[el].y=ye;

e[el].b=be;

e[el].d=0;

for(j=i,k=0;j;j>>=1,k+=3)

{

e[el].b+=(j&1)<<k;

}

cr[e[el].b>>3]|=(1<<(e[el].b&7));

el++;

}

while(eh!=el)

{

i=eh++;

if(e[i].d==30-D)

continue;

for(l=0;l<4;l++)

{

e[el].x=e[i].x+mv[l][0];

e[el].y=e[i].y+mv[l][1];

e[el].b=calc(e[i].b,e[i].x,e[i].y,

e[el].x,e[el].y,l);

e[el].d=e[i].d+1;

if(chk(e[el].x,e[el].y,e[el].b,cr))

{

cr[e[el].b>>3]|=(1<<(e[el].b&7));

if(!chk(e[el].x,e[el].y,e[el].b,c))

{

ans=e[el].d+D;

return;

}

el++;

}

void solve()

{

if((b&bm)==be)

{

puts("0");

return;

}

bfs();

if(ans<0x7fffffff)

{

printf("%d\n",ans);

return;

}

rbfs();

printf("%d\n",ans==0x7fffffff?-1:ans);

}

int main()

{

t['R']=2; t['W']=4; t['B']=6;

while(~scanf("%d%d",&x,&y)&&x)

{

init();

solve();

}

return 0;

}

虽然没有剪枝，但是内存全部静态分配并且大量使用位运算，程序非常的快（久违的刷到了第一）。

[POJ 3731]

发表回复

Escape

构造 + 组合

题意：在n*m的网格表示的街道图内，移动时需要走格线，每个交点最多可以经过一次，在交点处可以选择直行或右转。问从起点(0,0)出发到终点(x,y)最多有多少种走法。

这题想了很久也没头绪，然后看了看discuss里有人提示用”转弯次数”+”组合数”分类讨论，然后细心推了一下：从起点到终点之间的路径，总是纵横交错的。并且其中纵向部分，南北两向总是交替出现的；横向部分同理。通过进一步分析可以发现，若确定了一条路径的转弯次数，那么其中横向和纵向的部分是相互独立的，也即该转弯次数对应的路径总数为横向部分的方案数与纵向部分方案数的乘积。横向、纵向的方案数是可以分别通过组合数来计算出来的。在某方向上，每次拐弯的位置必须是交错地位于终点坐标两侧的，那么总方案数即为从两侧选择拐弯位置的总可能数。例如，横向坐标范围0~4，终点在3时，那么横向拐2次弯的总方案数为C(1,1)*C(3,1)，即先从4~4里面选一个位置拐一次，再从0~2里面选一个位置拐一次。不存在拐3次或以上弯的可能性。

到这里为止的推算还算是顺利的，倒是在计算C(n,k)上卡了很久的TLE。考虑了很久如何在模系统中实现除法，未果。于是开始分解质因数再累加，并想了各种优化……但都TLE了。最后才想起来可以利用C(n,k)=C(n-1,k)+C(n-1,k-1)来预处理出整个int C[2002][2002]，于是就AC了。

#include<cstdio>
#include<cstring>
#define M 100000007
#define ll long long

ll x,y,xe,ye,ans;
ll xd[2002],yd[2002];
ll c[2002][2002];

void init()
{
    ll i,j,k,l;
    for(i=0;i<2002;i++)
        for(j=c[i][0]=c[i][i]=1,k=i/2+1;j<k;j++)
            c[i][j]=c[i][i-j]=(c[i-1][j]+c[i-1][j-1])%M;
}

void solve()
{
    if(!xe&&!ye)
    {
        puts("1");
        return;
    }
    ll i,j,k,l;
    ll xl,xr,yb,yt;
    memset(xd,0,sizeof xd);
    memset(yd,0,sizeof yd);
    xl=xe-1; xr=x-xe;
    yb=ye; yt=y-ye;
    if(xe==0)
        xd[0]=1;
    if(ye==0)
        yd[0]=1;
    for(i=1;i<=x+1;i++)
    {
        j=(i-1)/2;
        k=(i-1)-j;
        xd[i]=c[xl][j]*c[xr][k]%M;
    }
    for(i=1;i<=y+1;i++)
    {
        j=(i-1)/2;
        k=(i-1)-j;
        yd[i]=c[yb][j]*c[yt][k]%M;
    }
    ans=yd[0]*xd[0];
    for(i=1;i<=x+1;i++)
        ans=(ans+yd[i]*(xd[i]+xd[i-1]))%M;
    printf("%lld\n",ans);
}

int main()
{
    init();
    scanf("%*d");
    while(~scanf("%lld%lld%lld%lld",&x,&y,&xe,&ye))
        solve();
    return 0;
}

#include<cstdio>

#include<cstring>

#define M 100000007

#define ll long long

ll x,y,xe,ye,ans;

ll xd[2002],yd[2002];

ll c[2002][2002];

void init()

{

ll i,j,k,l;

for(i=0;i<2002;i++)

for(j=c[i][0]=c[i][i]=1,k=i/2+1;j<k;j++)

c[i][j]=c[i][i-j]=(c[i-1][j]+c[i-1][j-1])%M;

}

void solve()

{

if(!xe&&!ye)

{

puts("1");

return;

}

ll i,j,k,l;

ll xl,xr,yb,yt;

memset(xd,0,sizeof xd);

memset(yd,0,sizeof yd);

xl=xe-1; xr=x-xe;

yb=ye; yt=y-ye;

if(xe==0)

xd[0]=1;

if(ye==0)

yd[0]=1;

for(i=1;i<=x+1;i++)

{

j=(i-1)/2;

k=(i-1)-j;

xd[i]=c[xl][j]*c[xr][k]%M;

}

for(i=1;i<=y+1;i++)

{

j=(i-1)/2;

k=(i-1)-j;

yd[i]=c[yb][j]*c[yt][k]%M;

}

ans=yd[0]*xd[0];

for(i=1;i<=x+1;i++)

ans=(ans+yd[i]*(xd[i]+xd[i-1]))%M;

printf("%lld\n",ans);

}

int main()

{

init();

scanf("%*d");

while(~scanf("%lld%lld%lld%lld",&x,&y,&xe,&ye))

solve();

return 0;

}

[POJ 1093]

发表回复

Formatting Text

题意：输入行长度值n，以及一篇文章，要将文章重新排版，使得”坏值”和最小。若某行只含一个单词，则坏值为500。包含多个单词的行，单词间每个长度为k的间隔，其坏值为(k-1)^2。

这题之前做CLRS时见过类似的（第二版习题15-2），当时也是想了很久才推出公式：用dp[i][j]保存到第i行结束时，打印了前j个单词的最小坏值。那么dp[i][j]=min{dp[i-1][k-1]+bd[n-sum{w[l]|k<=l<=j}][j-k]}，其中w[l]为第l个单词的长度，bd[p][q]为预处理计算出来的一行有p个空格和q个间隔时的坏值。状态转移时注意下标边界，并需要记录父状态。这里对于相同坏值的方案，要输出使各间隔长度值字典序最小的，那么每次dp使，总是使更多单词尽量在之前打印即可。输出时，首先找到最小坏值对应的行数，根据父状态一层层回退，记录每行要打印多少个单词；然后逐个单词处理输出即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define WN 1000

int n,sl,w[10000],wl,bd[81][81];
char s[10000];
int dp[WN][WN],p[WN][WN],dpi,dpj[WN],dpw[WN];

void init()
{
    int i,j,k,l;
    char c;
    sl=wl=0;
    memset(w,0,sizeof w);
    memset(s,0,sizeof s);
    memset(dp,-1,sizeof dp);
    getchar();
    while((c=getchar())!='\n')
    {
        while(c!='\n')
        {
            while(c==' ')
                c=getchar();
            if(c=='\n')
                break;
            while(c!=' '&&c!='\n')
            {
                w[wl]++;
                s[sl++]=c;
                c=getchar();
            }
            wl++;
        }
    }
}

void pnt(int wi,int si)
{
    int i;
    for(i=0;i<w[wi];i++)
        printf("%c",s[si+i]);
}

void pntw(int i)
{
    while(i--)
        printf(" ");
}

void solve()
{
    int i,j,k,l,pj,km;
    for(i=0,j=w[i];i<wl&&i+j<=n;i++,j+=w[i])
        dp[0][i]=bd[n-j][i];
    for(i=1;i<wl;i++)
    {
        for(j=i;j<wl&&dp[i-1][j-1]!=-1;j++)
        {
            for(k=j,l=w[k];k<wl&&l+k-j<=n;k++,l+=w[k])
            {
                if(dp[i][k]==-1)
                {
                    p[i][k]=j;
                    dp[i][k]=dp[i-1][j-1]+bd[n-l][k-j];
                }
                else if(dp[i-1][j-1]+bd[n-l][k-j]
                        <=dp[i][k])
                {
                    p[i][k]=j;
                    dp[i][k]=dp[i-1][j-1]+bd[n-l][k-j];
                }
            }
        }
    }
    for(i=0,j=0x7fffffff;i<wl;i++)
        if(dp[i][wl-1]!=-1)
        {
            if(dp[i][wl-1]<j)
            {
                j=dp[i][wl-1];
                dpi=i+1;
            }
        }
    dpj[dpi-1]=wl;
    for(i=dpi-1;i;i--)
        dpj[i-1]=p[i][dpj[i]-1];
    for(i=j=0;i<dpi;i++)
        for(dpw[i]=n;j<dpj[i];j++)
            dpw[i]-=w[j];
    for(i=j=pj=l=0;i<dpi;i++)
    {
        if(dpj[i]>j+1)
        {
            k=dpw[i]/(dpj[i]-j-1);
            km=(dpj[i]-j-1)-dpw[i]%(dpj[i]-j-1);
            for(;j<dpj[i]-1;j++)
            {
                pnt(j,l);
                l+=w[j];
                if(km)
                {
                    km--;
                    pntw(k);
                }
                else
                    pntw(k+1);
            }
        }
        pnt(j,l);
        l+=w[j];
        j++;
        puts("");
        pj=j;
    }
    puts("");
}

int main()
{
    int i,j,k,l;
    for(i=0;i<81;i++)
    {
        bd[i][0]=500;
        for(j=1;j<=i;j++)
        {
            k=i/j;
            if(i%j==0)
                bd[i][j]=j*(k-1)*(k-1);
            else
            {
                l=i%j;
                bd[i][j]=(j-l)*(k-1)*(k-1)+l*k*k;
            }
        }
    }
    while(~scanf("%d",&n)&&n)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define WN 1000

int n,sl,w[10000],wl,bd[81][81];

char s[10000];

int dp[WN][WN],p[WN][WN],dpi,dpj[WN],dpw[WN];

void init()

{

int i,j,k,l;

char c;

sl=wl=0;

memset(w,0,sizeof w);

memset(s,0,sizeof s);

memset(dp,-1,sizeof dp);

getchar();

while((c=getchar())!='\n')

{

while(c!='\n')

{

while(c==' ')

c=getchar();

if(c=='\n')

break;

while(c!=' '&&c!='\n')

{

w[wl]++;

s[sl++]=c;

c=getchar();

}

wl++;

}

void pnt(int wi,int si)

{

int i;

for(i=0;i<w[wi];i++)

printf("%c",s[si+i]);

}

void pntw(int i)

{

while(i--)

printf(" ");

}

void solve()

{

int i,j,k,l,pj,km;

for(i=0,j=w[i];i<wl&&i+j<=n;i++,j+=w[i])

dp[0][i]=bd[n-j][i];

for(i=1;i<wl;i++)

{

for(j=i;j<wl&&dp[i-1][j-1]!=-1;j++)

{

for(k=j,l=w[k];k<wl&&l+k-j<=n;k++,l+=w[k])

{

if(dp[i][k]==-1)

{

p[i][k]=j;

dp[i][k]=dp[i-1][j-1]+bd[n-l][k-j];

}

else if(dp[i-1][j-1]+bd[n-l][k-j]

<=dp[i][k])

{

p[i][k]=j;

dp[i][k]=dp[i-1][j-1]+bd[n-l][k-j];

}

for(i=0,j=0x7fffffff;i<wl;i++)

if(dp[i][wl-1]!=-1)

{

if(dp[i][wl-1]<j)

{

j=dp[i][wl-1];

dpi=i+1;

}

dpj[dpi-1]=wl;

for(i=dpi-1;i;i--)

dpj[i-1]=p[i][dpj[i]-1];

for(i=j=0;i<dpi;i++)

for(dpw[i]=n;j<dpj[i];j++)

dpw[i]-=w[j];

for(i=j=pj=l=0;i<dpi;i++)

{

if(dpj[i]>j+1)

{

k=dpw[i]/(dpj[i]-j-1);

km=(dpj[i]-j-1)-dpw[i]%(dpj[i]-j-1);

for(;j<dpj[i]-1;j++)

{

pnt(j,l);

l+=w[j];

if(km)

{

km--;

pntw(k);

}

else

pntw(k+1);

}

pnt(j,l);

l+=w[j];

j++;

puts("");

pj=j;

}

puts("");

}

int main()

{

int i,j,k,l;

for(i=0;i<81;i++)

{

bd[i][0]=500;

for(j=1;j<=i;j++)

{

k=i/j;

if(i%j==0)

bd[i][j]=j*(k-1)*(k-1);

else

{

l=i%j;

bd[i][j]=(j-l)*(k-1)*(k-1)+l*k*k;

}

while(~scanf("%d",&n)&&n)

{

init();

solve();

}

return 0;

}

ps: 这题考察的算法貌似很有实用价值呢……不过现在的文本处理程序，恐怕是要比这复杂十倍以上的吧……

[POJ 1324]

发表回复

Holedox Moving

搜索 + 滚动hash

给出最大20*20的格盘，和一条长为l的蛇，目的是使蛇头移动到(1,1)。格盘中存在k个格子是无法通过的石头，蛇也不能碰到自己的身体，包括最尾的一格。若能到(1,1)，输出最短距离，否则输出-1。

考虑保存蛇的状态时，只保存其蛇头位置，以及指向之前蛇头的指针。由此就能搜索处理蛇的移动方案。考虑判重时，使用滚动hash，即到一个新状态时，将之前蛇头对应的hash值升位并减去之前蛇尾的部分，再加上新的蛇头值即可。

另外就是，可以考虑优先向(1,1)的方向移动，以及搜索之前先判断蛇头是否可达(1,1)。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define HM 100003
#define HC 31
#define QL 100000
#define MEM 5000000

int t,n,m,pl,hl,hd[HM],el,mmx,mmy;
int mv[4][2]={-1,0,0,-1,1,0,0,1};
char s[20][20];
int q[QL],qh,qt;

struct H
{
    int x,y,d,p,u;
}h[MEM];

struct E
{
    int v,p;
}e[MEM];

inline void adde(int u,int v)
{
    e[el].v=v; e[el].p=hd[u]; hd[u]=el++;
}

inline bool chke()
{
    int i,j,k,l;
    for(l=hd[h[hl].u];l!=-1;l=e[l].p)
    {
        j=e[l].v;
        for(i=0,k=hl;i<pl;i++,j=h[j].p,k=h[k].p)
            if(h[j].x!=h[k].x||h[j].y!=h[k].y)
                break;
        if(i==pl)
            return 0;
    }
    return 1;
}

inline bool chk(int i,int j)
{
    if(i<0||i>=n||j<0||j>=m)
        return 0;
    if(s[i][j])
        return 0;
    return 1;
}

bool prechk()
{
    int i,j,k,l,x,y;
    char ss[20][20];
    memcpy(ss,s,sizeof ss);
    qh=qt=0;
    q[qh++]=0;
    s[0][0]=1;
    while(qt!=qh)
    {
        i=q[qt++];
        j=i/20;
        k=i%20;
        for(l=0;l<4;l++)
        {
            x=j+mv[l][0];
            y=k+mv[l][1];
            if(chk(x,y))
            {
                s[x][y]=1;
                q[qh++]=x*20+y;
            }
        }
    }
    i=s[h[0].x][h[0].y];
    memcpy(s,ss,sizeof ss);
    return i;
}

int bfs()
{
    int i,j,k,l,x,y;
    if(h[0].x==0&&h[0].y==0)
        return 0;
    q[qh++]=0;
    while(qt!=qh)
    {
        i=q[qt++];
        if(qt==QL)
            qt=0;
        for(j=0,k=i;j<pl;j++,k=h[k].p)
            s[h[k].x][h[k].y]=1;
        for(l=0;l<4;l++)
        {
            x=h[i].x+mv[l][0];
            y=h[i].y+mv[l][1];
            if(chk(x,y))
            {
                if(x==0&&y==0)
                    return h[i].d+1;
                h[hl].x=x;
                h[hl].y=y;
                h[hl].d=h[i].d+1;
                h[hl].p=i;
                for(j=1,k=i;j<pl;j++,k=h[k].p);
                h[hl].u=(h[i].u*HC*HC-mmx*h[k].x-mmy*h[k].y
                        +HC*x+y)%HM;
                if(h[hl].u<0)
                    h[hl].u+=HM;
                if(chke())
                {
                    adde(h[hl].u,hl);
                    q[qh++]=hl++;
                    if(qh==QL)
                        qh=0;
                }
            }
        }
        for(j=0,k=i;j<pl;j++,k=h[k].p)
            s[h[k].x][h[k].y]=0;
    }
    return -1;
}

void init()
{
    int i,j,k,l;
    hl=el=0;
    qh=qt=0;
    memset(s,0,sizeof s);
    memset(hd,-1,sizeof hd);
    for(i=0,mmy=1;i<pl*2;i++)
        mmy=(mmy*HC)%HM;
    mmx=mmy*HC%HM;
    for(hl=0;hl<pl;hl++)
    {
        scanf("%d%d",&j,&k);
        h[hl].x=j-1;
        h[hl].y=k-1;
        h[hl].p=hl+1;
    }
    h[0].d=0;
    for(i=pl-1,j=0;i>-1;i--)
    {
        j=(j*HC+h[i].x)%HM;
        j=(j*HC+h[i].y)%HM;
    }
    h[0].u=j;
    adde(j,0);
    scanf("%d",&l);
    while(l--)
    {
        scanf("%d%d",&i,&j);
        s[i-1][j-1]=1;
    }
}

void solve()
{
    if(!prechk())
        printf("Case %d: -1\n",++t);
    else
        printf("Case %d: %d\n",++t,bfs());
}

int main()
{
    while(~scanf("%d%d%d",&n,&m,&pl)&&n)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define HM 100003

#define HC 31

#define QL 100000

#define MEM 5000000

int t,n,m,pl,hl,hd[HM],el,mmx,mmy;

int mv[4][2]={-1,0,0,-1,1,0,0,1};

char s[20][20];

int q[QL],qh,qt;

struct H

{

int x,y,d,p,u;

}h[MEM];

struct E

{

int v,p;

}e[MEM];

inline void adde(int u,int v)

{

e[el].v=v; e[el].p=hd[u]; hd[u]=el++;

}

inline bool chke()

{

int i,j,k,l;

for(l=hd[h[hl].u];l!=-1;l=e[l].p)

{

j=e[l].v;

for(i=0,k=hl;i<pl;i++,j=h[j].p,k=h[k].p)

if(h[j].x!=h[k].x||h[j].y!=h[k].y)

break;

if(i==pl)

return 0;

}

return 1;

}

inline bool chk(int i,int j)

{

if(i<0||i>=n||j<0||j>=m)

return 0;

if(s[i][j])

return 0;

return 1;

}

bool prechk()

{

int i,j,k,l,x,y;

char ss[20][20];

memcpy(ss,s,sizeof ss);

qh=qt=0;

q[qh++]=0;

s[0][0]=1;

while(qt!=qh)

{

i=q[qt++];

j=i/20;

k=i%20;

for(l=0;l<4;l++)

{

x=j+mv[l][0];

y=k+mv[l][1];

if(chk(x,y))

{

s[x][y]=1;

q[qh++]=x*20+y;

}

i=s[h[0].x][h[0].y];

memcpy(s,ss,sizeof ss);

return i;

}

int bfs()

{

int i,j,k,l,x,y;

if(h[0].x==0&&h[0].y==0)

return 0;

q[qh++]=0;

while(qt!=qh)

{

i=q[qt++];

if(qt==QL)

qt=0;

for(j=0,k=i;j<pl;j++,k=h[k].p)

s[h[k].x][h[k].y]=1;

for(l=0;l<4;l++)

{

x=h[i].x+mv[l][0];

y=h[i].y+mv[l][1];

if(chk(x,y))

{

if(x==0&&y==0)

return h[i].d+1;

h[hl].x=x;

h[hl].y=y;

h[hl].d=h[i].d+1;

h[hl].p=i;

for(j=1,k=i;j<pl;j++,k=h[k].p);

h[hl].u=(h[i].u*HC*HC-mmx*h[k].x-mmy*h[k].y

+HC*x+y)%HM;

if(h[hl].u<0)

h[hl].u+=HM;

if(chke())

{

adde(h[hl].u,hl);

q[qh++]=hl++;

if(qh==QL)

qh=0;

}

for(j=0,k=i;j<pl;j++,k=h[k].p)

s[h[k].x][h[k].y]=0;

}

return -1;

}

void init()

{

int i,j,k,l;

hl=el=0;

qh=qt=0;

memset(s,0,sizeof s);

memset(hd,-1,sizeof hd);

for(i=0,mmy=1;i<pl*2;i++)

mmy=(mmy*HC)%HM;

mmx=mmy*HC%HM;

for(hl=0;hl<pl;hl++)

{

scanf("%d%d",&j,&k);

h[hl].x=j-1;

h[hl].y=k-1;

h[hl].p=hl+1;

}

h[0].d=0;

for(i=pl-1,j=0;i>-1;i--)

{

j=(j*HC+h[i].x)%HM;

j=(j*HC+h[i].y)%HM;

}

h[0].u=j;

adde(j,0);

scanf("%d",&l);

while(l--)

{

scanf("%d%d",&i,&j);

s[i-1][j-1]=1;

}

void solve()

{

if(!prechk())

printf("Case %d: -1\n",++t);

else

printf("Case %d: %d\n",++t,bfs());

}

int main()

{

while(~scanf("%d%d%d",&n,&m,&pl)&&n)

{

init();

solve();

}

return 0;

}