Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstdlib>
- #include <cmath>
- #include <vector>
- #include <map>
- #include <set>
- #include <queue>
- #include <string>
- #include <cstring>
- #include <cassert>
- #include <ctime>
- using namespace std;
- #ifdef LOCAL
- #define eprintf(...) printf(__VA_ARGS__)
- #else
- #define eprintf(...) 0
- #endif
- const int N = 15;
- const int EMPTY = 0;
- const int GOOD = 1;
- const int BAD = -1;
- const int DX[] = { -1, 0, 1, 0 };
- const int DY[] = { 0, -1, 0, 1 };
- int n, w, h;
- struct Point
- {
- int x, y;
- Point(int _x, int _y) : x(_x), y(_y) {}
- };
- struct Figure
- {
- int used[N][N];
- int min_y_in_first_row;
- vector<Point> points;
- Figure() : used(), min_y_in_first_row() {}
- int get_cnt()
- {
- return (int)points.size();
- }
- void set(int x, int y, int mark)
- {
- used[x][y] = mark;
- if (mark == GOOD)
- points.push_back(Point(x, y));
- }
- void unset(int x, int y)
- {
- if (used[x][y] == GOOD)
- points.pop_back();
- used[x][y] = EMPTY;
- }
- bool already_nice()
- {
- int mn = 1;
- for (Point p : points)
- mn = min(mn, p.y);
- return mn == 0;
- }
- };
- bool in_field(int x, int y)
- {
- return x >= 0 && x < w && y >= 0 && y < h;
- }
- int ans;
- void add_figure(Figure f)
- {
- ans++;
- }
- void bruteforce(Figure & f)
- {
- int cnt = f.get_cnt();
- if (cnt == n)
- {
- if (!f.already_nice())
- return;
- add_figure(f);
- return;
- }
- for (Point p : f.points)
- {
- for (int d = 0; d < 4; d++)
- {
- int nx = p.x + DX[d];
- int ny = p.y + DY[d];
- if (!in_field(nx, ny))
- continue;
- if (nx == 0 && ny < f.min_y_in_first_row)
- continue;
- if (f.used[nx][ny] != EMPTY)
- continue;
- f.set(nx, ny, GOOD);
- bruteforce(f);
- f.unset(nx, ny);
- f.set(nx, ny, BAD);
- bruteforce(f);
- f.unset(nx, ny);
- }
- }
- }
- void solve()
- {
- scanf("%d%d%d", &n, &w, &h);
- for (int y = 0; y < h; y++)
- {
- Figure f;
- f.min_y_in_first_row = y;
- f.set(0, y, GOOD);
- bruteforce(f);
- }
- printf("%d\n", ans);
- }
- int main()
- {
- freopen("lattice.in", "r", stdin);
- freopen("lattice.out", "w", stdout);
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement