Advertisement
Guest User

Untitled

a guest
Nov 26th, 2014
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <algorithm>
  6. #include <cstdlib>
  7. #include <cmath>
  8. #include <vector>
  9. #include <map>
  10. #include <set>
  11. #include <queue>
  12. #include <string>
  13. #include <cstring>
  14. #include <cassert>
  15. #include <ctime>
  16. using namespace std;
  17.  
  18. #ifdef LOCAL
  19. #define eprintf(...) printf(__VA_ARGS__)
  20. #else
  21. #define eprintf(...) 0
  22. #endif
  23.  
  24. const int N = 15;
  25. const int EMPTY = 0;
  26. const int GOOD = 1;
  27. const int BAD = -1;
  28.  
  29. const int DX[] = { -1, 0, 1, 0 };
  30. const int DY[] = { 0, -1, 0, 1 };
  31.  
  32. int n, w, h;
  33.  
  34. struct Point
  35. {
  36.     int x, y;
  37.  
  38.     Point(int _x, int _y) : x(_x), y(_y) {}
  39. };
  40.  
  41. struct Figure
  42. {
  43.     int used[N][N];
  44.     int min_y_in_first_row;
  45.     vector<Point> points;
  46.  
  47.     Figure() : used(), min_y_in_first_row() {}
  48.  
  49.     int get_cnt()
  50.     {
  51.         return (int)points.size();
  52.     }
  53.  
  54.     void set(int x, int y, int mark)
  55.     {
  56.         used[x][y] = mark;
  57.         if (mark == GOOD)
  58.             points.push_back(Point(x, y));
  59.     }
  60.  
  61.     void unset(int x, int y)
  62.     {
  63.         if (used[x][y] == GOOD)
  64.             points.pop_back();
  65.         used[x][y] = EMPTY;
  66.     }
  67.  
  68.     bool already_nice()
  69.     {
  70.         int mn = 1;
  71.         for (Point p : points)
  72.             mn = min(mn, p.y);
  73.         return mn == 0;
  74.     }
  75. };
  76.  
  77. bool in_field(int x, int y)
  78. {
  79.     return x >= 0 && x < w && y >= 0 && y < h;
  80. }
  81.  
  82. int ans;
  83. void add_figure(Figure f)
  84. {
  85.     ans++;
  86. }
  87.  
  88. void bruteforce(Figure & f)
  89. {
  90.     int cnt = f.get_cnt();
  91.     if (cnt == n)
  92.     {
  93.         if (!f.already_nice())
  94.             return;
  95.         add_figure(f);
  96.         return;
  97.     }
  98.  
  99.     for (Point p : f.points)
  100.     {
  101.         for (int d = 0; d < 4; d++)
  102.         {
  103.             int nx = p.x + DX[d];
  104.             int ny = p.y + DY[d];
  105.             if (!in_field(nx, ny))
  106.                 continue;
  107.             if (nx == 0 && ny < f.min_y_in_first_row)
  108.                 continue;
  109.             if (f.used[nx][ny] != EMPTY)
  110.                 continue;
  111.  
  112.             f.set(nx, ny, GOOD);
  113.             bruteforce(f);
  114.             f.unset(nx, ny);
  115.  
  116.             f.set(nx, ny, BAD);
  117.             bruteforce(f);
  118.             f.unset(nx, ny);
  119.         }
  120.     }
  121. }
  122.  
  123. void solve()
  124. {
  125.     scanf("%d%d%d", &n, &w, &h);
  126.     for (int y = 0; y < h; y++)
  127.     {
  128.         Figure f;
  129.         f.min_y_in_first_row = y;
  130.         f.set(0, y, GOOD);
  131.         bruteforce(f);
  132.     }
  133.     printf("%d\n", ans);
  134. }
  135.  
  136. int main()
  137. {
  138.     freopen("lattice.in", "r", stdin);
  139.     freopen("lattice.out", "w", stdout);
  140.  
  141.     solve();
  142.  
  143.     return 0;
  144. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement