fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5.  
  6. long long dp[200][2 << 14];
  7.  
  8. class DominoTiling {
  9. public:
  10. 	long long count(vector<string>V) {
  11. 		int H = V.size(), W = V[0].size();
  12. 		dp[0][0] = 1;
  13. 		for (int i = 0; i < H*W; i++) {
  14. 			int cx = i / W, cy = i%W;
  15. 			for (int j = 0; j < (1 << W); j++) {
  16. 				if (V[cx][cy] == 'X' || (j&(1 << cy)) != 0) {
  17. 					if ((j&(1 << cy)) == 0)dp[i + 1][j] += dp[i][j];
  18. 					else dp[i + 1][j - (1 << cy)] += dp[i][j];
  19. 				}
  20. 				else {
  21. 					if (cy < W - 1 && V[cx][cy + 1] != 'X' && (j&(1 << (cy + 1))) == 0)dp[i + 1][j + (1 << (cy + 1))] += dp[i][j];
  22. 					if (cx < H - 1 && V[cx + 1][cy] != 'X' && (j&(1 << cy)) == 0)dp[i + 1][j + (1 << cy)] += dp[i][j];
  23. 				}
  24. 			}
  25. 		}
  26. 		return dp[H*W][0];
  27. 	}
  28. };
  29. int main() {
  30. 	DominoTiling eel;
  31. 	cout << eel.count({ "....","....","....","...." }) << endl;
  32. 	return 0;
  33. }
Success #stdin #stdout 0s 66432KB
comments (?)
stdin 
Standard input is empty
stdout 
36
https://ideone.com/umRkMk
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!