/* -*- coding: utf-8 -*- * * 3710.cc: No.3710 Universal Tiles - yukicoder */ #include #include #include using namespace std; /* constant */ const int MAX_N = 8; const int MAX_M = 10; const int INF = 1 << 30; /* typedef */ using btst = bitset; using mat = btst[MAX_M]; /* global variables */ mat ss[MAX_N][4]; int ps[MAX_N]; /* subroutines */ void rotmat(const int m, const mat a, mat b) { for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) b[m - 1 - j][i] = a[i][j]; } void ormat(const int m, const mat a, mat b) { for (int i = 0; i < m; i++) b[i] |= a[i]; } /* main */ int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { char s[MAX_M + 4]; scanf("%s", s); for (int k = 0; k < m; k++) ss[i][0][j][k] = (s[k] == '#'); } for (int i = 0; i < n; i++) for (int d = 1; d < 4; d++) rotmat(m, ss[i][d - 1], ss[i][d]); int minsum = INF; for (;;) { mat t; for (int i = 0; i < n; i++) ormat(m, ss[i][ps[i]], t); int sum = 0; for (int j = 0; j < m; j++) sum += t[j].count(); minsum = min(minsum, sum); int k = 0; while (k < n) { if (++ps[k] > 3) ps[k++] = 0; else break; } if (k >= n) break; } printf("%d\n", minsum); return 0; }