题意:在一个坐标系的原点出发走 k 步回到原点,第 i 步走 i 个单位长度。有 x 个障碍,障碍不能经过或者停留。每一步结束的地方不能再作为结束的地方。求有多少中方案以及每个方案的移动序列(用 wsne 表示),按字典序输出。

分析:垃圾题面毁我青春!它竟然没有说清楚不能在停留过的点停留!

所以我们建立一个二维数组 (起名叫 mp) 进行判重。mp[x][y]==1 表示有障碍,mp[x][y]==2 表示停留过。搜索时判断经过的每个点是否为障碍,再判断结束点是否停留过。

剪枝:如果当前距离原点的距离大于以后可以走的总距离,则停止继续搜索。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

#define MC 251

using namespace std;

int maxl,block;
short mp[MC][MC];
int T;
short nxt[5][3]= {{0,0,0},{0,1,0},{0,0,1},{0,0,-1},{0,-1,0}};
char dir[6]="hensw",route[100];
int ansnum;

typedef struct p
{
    int x,y;
} pot;
pot targ;

int input()
{
    int a,b;
    memset(mp,0,sizeof(mp));
    scanf("%d%d",&maxl,&block);
    for(int i=1; i<=block; i++)
    {
        scanf("%d%d",&a,&b);
        mp[a+MC][b+MC]=1;
    }
    return maxl;
}

int dist(pot a,pot b)
{
    return abs(a.x-b.x)+abs(a.y-b.y);
}

int trymove(pot from,pot to)
{
    if(from.x==to.x)
    {
        for(int i=min(from.y,to.y)+MC; i<=max(from.y,to.y)+MC; i++)
            if(mp[from.x+MC][i]==1)
                return 0;
        if(mp[to.x+MC][to.y+MC]==2)return 0;
    }
    else
    {
        for(int i=min(from.x,to.x)+MC; i<=max(from.x,to.x)+MC; i++)
            if(mp[i][from.y+MC]==1)
                return 0;
        if(mp[to.x+MC][to.y+MC]==2)return 0;
    }
    return 1;
}

void sch(int d,int last,pot now)
{
    pot next;
    if(now.x==targ.x&&now.y==targ.y&&d==maxl)
    {
        printf("%s\n",route);
        ansnum++;
        return;
    }
    if((maxl-d)*(d+1+maxl)/2<dist(now,targ))return;
    for(int i=1; i<=4; i++)
    {
        if(i!=last&&i!=5-last)
        {
            next.x=now.x+nxt[i][1]*(d+1);
            next.y=now.y+nxt[i][2]*(d+1);
            if(trymove(now,next))
            {
                mp[next.x+MC][next.y+MC]=2,route[d]=dir[i];
                sch(d+1,i,next);
                mp[next.x+MC][next.y+MC]=0;
            }
        }
    }
}

int main()
{
    pot start;
    scanf("%d",&T);
    for(int i=1; i<=T; i++)
    {
        input();
        ansnum=0,targ.x=0,targ.y=0,start.x=0,start.y=0;
        memset(route,0,sizeof(route));
        sch(0,0,start);
        printf("Found %d golygon(s).\n\n",ansnum);
    }
    return 0;
}

其实本题还可以继续优化:

1. 使用中途相遇法,先走 k/2 步(或者说 2k/1.414 步),保存到大的点和上一步走的方向。再从原点走 k/2(或者说 1-2k/1.414)步, 在上一次搜索到的点中寻找可行的 “拼接”,生成行动序列。

2. 使用前缀和优化判断移动是否可行的过程。对 mp 的每一行每一列计算前缀和,即可将每一个序列的均摊判断复杂度的 O(N2) 优化成 O(N);

不过这两个优化只是特别小的优化,没有显著效果。第一个实在就不值得实现了。第二个实现后将 300ms 优化成了 270mn 也算是有点用吧

优化后代码↓

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

#define MC 251

using namespace std;

int maxl,block;
short mp[MC*2][MC*2],xqzh[MC*2][MC*2],yqzh[MC*2][MC*2];
int T;
short nxt[5][3]= {{0,0,0},{0,1,0},{0,0,1},{0,0,-1},{0,-1,0}};
char dir[6]="hensw",route[100];
int ansnum;

typedef struct p
{
    int x,y;
} pot;
pot targ;

int input()
{
    int a,b;
    memset(mp,0,sizeof(mp));
    scanf("%d%d",&maxl,&block);
    for(int i=1; i<=block; i++)
    {
        scanf("%d%d",&a,&b);
        mp[a+MC][b+MC]=1;
    }
    for(int i=1;i<=MC*2-1;i++)
        for(int j=1;j<=MC*2-1;j++)
            xqzh[i][j]=xqzh[i][j-1]+mp[i][j],yqzh[j][i]=yqzh[j][i-1]+mp[i][j];
    return maxl;
}

int dist(pot a,pot b)
{
    return abs(a.x-b.x)+abs(a.y-b.y);
}

int trymove(pot from,pot to)
{
    int l,r;
    if(from.x==to.x)
    {
        l=min(to.y,from.y),r=to.y+from.y-l;
        if(xqzh[to.x+MC][l-1+MC]!=xqzh[from.x+MC][r+MC]||mp[to.x+MC][to.y+MC]==2)return 0;
    }
    else
    {
        l=min(to.x,from.x),r=to.x+from.x-l;
        if(yqzh[to.y+MC][l-1+MC]!=yqzh[from.y+MC][r+MC]||mp[to.x+MC][to.y+MC]==2)return 0;
    }
    return 1;
}

void sch(int d,int last,pot now)
{
    pot next;
    if(now.x==targ.x&&now.y==targ.y&&d==maxl)
    {
        printf("%s\n",route);
        ansnum++;
        return;
    }
    if((maxl-d)*(d+1+maxl)/2<dist(now,targ))return;
    for(int i=1; i<=4; i++)
    {
        if(i!=last&&i!=5-last)
        {
            next.x=now.x+nxt[i][1]*(d+1),next.y=now.y+nxt[i][2]*(d+1);
            if(trymove(now,next))
            {
                mp[next.x+MC][next.y+MC]=2;
                route[d]=dir[i];
                sch(d+1,i,next);
                mp[next.x+MC][next.y+MC]=0;
            }
        }
    }
}

int main()
{
    pot start;
    scanf("%d",&T);
    for(int i=1; i<=T; i++)
    {
        input();
        ansnum=0,targ.x=0,targ.y=0,start.x=0,start.y=0;
        memset(route,0,sizeof(route));
        sch(0,0,start);
        printf("Found %d golygon(s).\n\n",ansnum);
    }
    return 0;
}
分类: 文章

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注