UVa 225 - Golygons（DFS＋回溯）

发表于 分类于 ， Disqus：

在一个平面上从原点出发，走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博客，格式可能有所偏差。 **

相关文章