v 0. Pasted by slipstak2 as cpp at 2011-10-28 20:56:57 MSK and set expiration to never.

Paste will expire never.

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <string>
  5. #include <string.h>
  6. #include <cmath>
  7. #include <queue>
  8. #include <vector>
  9. #include <map>
  10. #include <stdlib.h> // for exit(0)
  11. #include <stack>
  12. #include <list>
  13. #include <ctime>
  14. #include <set>
  15.  
  16. using namespace std;
  17.  
  18. const int MAX_HEIGHT = 5;
  19. const int MAX_MASK = (1 << MAX_HEIGHT) - 1;
  20. bool adj_mask[MAX_MASK + 1][MAX_MASK + 1];
  21. int dp[35][MAX_MASK + 1];
  22. int MASK;
  23. int n,m;
  24. void input(){
  25.     scanf("%d %d", &n, &m);
  26.     if(n > m) swap(n,m);
  27.     MASK = (1 << n) - 1;
  28. }
  29. inline int get_bit(int num, int bit) {
  30.     return num & (1 << bit) ? 1 : 0;
  31. }
  32. void precalc_matrix() {
  33.     for (int prv = 0; prv <= MASK; ++prv) {
  34.         for (int cur = 0; cur <= MASK; ++cur) {
  35.             bool isComp = true;
  36.             for (int bit = 0; bit < n - 1; ++bit) {
  37.                 int sum = get_bit(prv,bit) + get_bit(prv, bit + 1) +
  38.                           get_bit(cur,bit) + get_bit(cur, bit + 1);
  39.                 if (sum == 0 || sum == 4) {
  40.                     isComp = false;
  41.                     break;
  42.                 }
  43.             }
  44.             adj_mask[prv][cur] = isComp;
  45.         }
  46.     }
  47. }
  48. void solve(){
  49.     for (int mask = 0; mask <= MASK; ++mask)
  50.         dp[0][mask] = 1;
  51.     for (int k = 1; k < m; ++k) {
  52.         for (int prv = 0; prv <= MASK; ++prv) {
  53.             for (int cur = 0; cur <= MASK; ++cur) {
  54.                 if (adj_mask[prv][cur])
  55.                     dp[k][cur] += dp[k-1][prv];
  56.             }
  57.         }
  58.     }
  59. }
  60. void output() {
  61.     int res = 0;
  62.     for (int mask = 0; mask <= MASK; ++mask)
  63.         res += dp[m-1][mask];
  64.     printf("%d", res);
  65. }
  66. int main()
  67. {
  68.     freopen("input.txt","r",stdin);
  69.     freopen("output.txt","w",stdout);
  70.  
  71.     input();
  72.     precalc_matrix();
  73.     solve();
  74.     output();
  75.  
  76.     return 0;
  77. }


Editing is locked.