Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <numeric>
- using namespace std;
- typedef long long ll;
- bool bit(ll var, int pos) {
- return ((var >> pos) & 1);
- }
- int main() {
- ifstream fin("input.txt");
- ofstream fout("output.txt");
- int n, m; fin >> n >> m;
- if (n > m)
- swap(n, m);
- vector<vector<ll>> dp(m, vector<ll>(1 << n));
- for (int i = 0; i < (1 << n); i++) dp[0][i] = 1;
- for (int i = 0; i < m - 1; i++) {
- for (int prof = 0; prof < (1 << n); prof++) {
- for (int next_prof = 0; next_prof < (1 << n); next_prof++) {
- bool f = 1;
- for (int k = 0; k < n - 1; k++)
- if (bit(prof, k) == bit(next_prof, k) && bit(next_prof, k) == bit(prof, k + 1) && bit(prof, k + 1) == bit(next_prof, k + 1)) {
- f = 0; break;
- }
- dp[i + 1][next_prof] += dp[i][prof] * f;
- }
- }
- }
- fout << accumulate(dp[m - 1].begin(), dp[m - 1].end(), 0) << endl;
- fin.close();
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment