UVa 225 - Golygons(DFS+回溯)

在一个平面上从原点出发,走n步,第i步走的距离为i,每一步都必须转向90度。有k个障碍物,不能穿过。给出步数和障碍物位置,问有多少种可行路径。

输入有负数,但仍然可以使用数组,将g[maxn][maxn]作为原点。(x,y)用g[maxn+x][maxn+y]表示。

进行DFS,注意是否有障碍物,当剩下的步数走不回原点时,回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxm=25,maxn=250;
const char s[]="ensw";
const int go[2][4]={{1,0,0,-1},{0,1,-1,0}};
int n,cnt,sum[maxm];
bool g[maxn*2][maxn*2],vis[maxn*2][maxn*2];
char s0[maxm];
void read(){
int k;
cin>>n>>k;
while(k--){
int x,y;
cin>>x>>y;
if(abs(x)>=maxn||abs(y)>=maxn) continue;
g[maxn+x][maxn+y]=true;//g[maxn+x][maxn+y]表示(x,y)。
}
return;
}
bool cdt(int x1,int y1,int x2,int y2){//判断是否经过障碍物。
if(x1==x2){
int x=x1+maxn,maxy=maxn+max(y1,y2);
for(int y=maxn+min(y1,y2);y<=maxy;y++){
if(g[x][y]) return true;
}
}
if(y1==y2){
int y=y1+maxn,maxx=maxn+max(x1,x2);
for(int x=maxn+min(x1,x2);x<=maxx;x++){
if(g[x][y]) return true;
}
}
return false;
}
void dfs(int cur,int last_x,int last_y,int last_dir){
int dist=abs(last_x)+abs(last_y);
if(dist>sum[n]-sum[cur]) return;//剩下步数回不到原点,回溯。
if(cur==n){
if(dist) return;
cout<<s0<<endl;
cnt++;
return;
}
for(int i=0;i<4;i++){
if(i==last_dir||i==3-last_dir) continue;
int cur_x=last_x+go[0][i]*(cur+1),cur_y=last_y+go[1][i]*(cur+1);
if(cdt(last_x,last_y,cur_x,cur_y)) continue;
if(!vis[maxn+cur_x][maxn+cur_y]){
s0[cur]=s[i];
vis[maxn+cur_x][maxn+cur_y]=true;
dfs(cur+1,cur_x,cur_y,i);
vis[maxn+cur_x][maxn+cur_y]=false;
s0[cur]=0;
}
}
return;
}
int main(){
ios::sync_with_stdio(false);
int t;
cin>>t;
for(int i=1;i<maxm;i++) sum[i]=sum[i-1]+i;
while(t--){
cnt=0;
memset(vis,0,sizeof(vis));
memset(s0,0,sizeof(s0));
memset(g,0,sizeof(g));
read();
if((n>14&&n<17)||(n>6&&n<9))//n不为这些值时,没有解。
dfs(0,0,0,-1);
cout<<"Found "<<cnt<<" golygon(s)."<<endl<<endl;
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。