#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using ll = long long; using namespace std; using namespace __gnu_pbds; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const double pi = acos(-1); const int N = 12 + 1, K = 80 + 1, SQ = 500, M = 1e9 + 7; //#define TESTS //#define INTERACTIVE //#define COMMUNICATION /* * Remember who you are. */ void pre() { } string c[2 * N]; int dp[N][K][1 << N][2], vis[N][K][1 << N][2], n, m, vid; int rec(int i, int j, int mask, bool up) { if (i == n / 2) return up ? (int) 1e9 : rec(0, j + 1, mask, 0); if (j == m / 2) return 0; auto &ret = dp[i][j][mask][up]; auto &v = vis[i][j][mask][up]; if (v == vid) return ret; ret = 1e9; v = vid; char cur = c[2 * i + 1][2 * j + 1]; char bot = c[2 * i + 2][2 * j + 1]; char right = c[2 * i + 1][2 * j + 2]; if (cur == 'X') { if (up && (~mask >> i & 1)) ret = min(ret, rec(i + 1, j, mask, false) + 1); else if (!up) { if (mask >> i & 1) ret = min(ret, rec(i + 1, j, mask ^ (1 << i), false) + 1); else { if (bot == ' ') ret = min(ret, rec(i + 1, j, mask, true) + 1); if (right == ' ') ret = min(ret, rec(i + 1, j, mask | (1 << i), false) + 1); } } } else { if (up) { if (mask >> i & 1) ret = min(ret, rec(i + 1, j, mask ^ (1 << i), false) + 2); else { if (bot == ' ') ret = min(ret, rec(i + 1, j, mask, true) + 2); if (right == ' ') ret = min(ret, rec(i + 1, j, mask | (1 << i), false) + 2); } } else { if (mask >> i & 1) { if (bot == ' ') ret = min(ret, rec(i + 1, j, mask ^ (1 << i), true) + 2); if (right == ' ') ret = min(ret, rec(i + 1, j, mask, false) + 2); } else { ret = min(ret, rec(i + 1, j, mask, false)); if (bot == ' ' && right == ' ') ret = min(ret, rec(i + 1, j, mask | (1 << i), true) + 2); } } } return ret; } void solve() { cin >> n >> m; cin.ignore(); for (int i = 0; i < n; ++i) getline(cin, c[i]); ++vid; cout << rec(0, 0, 0, false); } void solve2() { } signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); #ifdef CAROOT #ifndef INTERACTIVE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif #else #endif int tt = 1; pre(); #ifdef COMMUNICATION string run; cin >> run; #endif #ifdef TESTS cin >> tt; #endif for (int tc = 1; tc <= tt; ++tc) { #ifdef COMMUNICATION if (run == "first") solve(); else solve2(); #else solve(); #endif cout << '\n'; } }