解題區/解題區 - UVa

UVa 225 - Golygons

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

每一步轉角九十度，並且第 i 次要走 i 長單位，回到原點且沿途不經過障礙物，同時轉角不可重複。

Sample Input

1
2
3
4
5
6
7
8
9
2
8
2
-2 0
6 -2
8
2
2 1
-2 0

Sample Output

1
2
3
4
wsenenws
Found 1 golygon(s).
Found 0 golygon(s).

Solution

沿途經過障礙物，同時轉角不重複。一開始曲解了經過的轉角點，以為他也不能在隨後中經過，但實際上是可以的，因此拿了不少 WA。

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h> 
#include <stdlib.h>
#include <algorithm>
#include <set>
#include <vector>
#include <iostream>
#include <assert.h>
using namespace std;
int n, m, golygons;
set< pair<int, int> > ban;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const char sdir[] = "nsew";
char path[1024];
char g[2048][2048] = {}, g2[2048][2048];
vector<string> ways;
#define BASE 1024
void dfs(int x, int y, int dir, int step) {
    if (abs(x - 0) + abs(y - 0) > (step + n) * (n - step + 1)/2) {
        return;
    }
    if (step == n + 1) {
        if (x == 0 && y == 0) {
            path[step - 1] = '\0';
//			puts(path);
            ways.push_back(path);
            golygons++;
        }
        return ;
    }
    if (dir != 0) {
        for (int i = 0; i < 2; i++) {
            int tx = x, ty = y, ok = 1;
            for (int j = 0; j < step; j++) {
                tx = tx + dx[i], ty = ty + dy[i];
                assert(BASE + tx >= 0 && BASE + ty >= 0);
                assert(BASE + tx < 2048 && BASE + ty < 2048);
                if (g[BASE + tx][BASE + ty]) {
                    ok = 0;
                    break;
                }
            }
            if (ok && g2[BASE + tx][BASE + ty] == 0) {
                g2[BASE + tx][BASE + ty] = 1;
                path[step - 1] = sdir[i];
                dfs(tx, ty, 0, step + 1);
                g2[BASE + tx][BASE + ty] = 0;
            }
        }
    }
    if (dir != 1) {
        for (int i = 2; i < 4; i++) {
            int tx = x, ty = y, ok = 1;
            for (int j = 0; j < step; j++) {
                tx = tx + dx[i], ty = ty + dy[i];
                assert(BASE + tx >= 0 && BASE + ty >= 0);
                assert(BASE + tx < 2048 && BASE + ty < 2048);
                if (g[BASE + tx][BASE + ty]) {
                    ok = 0;
                    break;
                }
            }
            if (ok && g2[BASE + tx][BASE + ty] == 0) {
                g2[BASE + tx][BASE + ty] = 1;
                path[step - 1] = sdir[i];
                dfs(tx, ty, 1, step + 1);
                g2[BASE + tx][BASE + ty] = 0;
            }
        }
    }
}
int main() {
    int testcase, x[64], y[64];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        ban.clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x[i], &y[i]);
            ban.insert(make_pair(x[i], y[i]));
            g[BASE + x[i]][BASE + y[i]] = 1;
        }
        ways.clear();
        dfs(0, 0, -1, 1);
        sort(ways.begin(), ways.end());
        for (int i = 0; i < ways.size(); i++)
            puts(ways[i].c_str());
        printf("Found %d golygon(s).\n\n", ways.size());
        for (int i = 0; i < m; i++)
            g[BASE + x[i]][BASE + y[i]] = 0;
    }
    return 0;
}
/*
2
8
2
-2 0
6 -2
8
2
2 1
-2 0
1000
16
0
*/