题意：在一个坐标系的原点出发走 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 条评论