Explode 'Em All 22.08.13

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <bitset>
#include <iostream>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

int n, m, m1, m2, h[60], rm[2][10000], ans = 9000;
char c[30][30];

int ones(int n, int m) {
    int r = 0;
    for (int i = 0; n && (i < m); i++) {
        r += n & 1;
        n >>= 1;
    }
    return r;
}

int v[2][100000];

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    scanf("%d%d\n", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            scanf("%c", &c[i][j]);
        scanf("\n");
    }

    m2 = m >> 1;
    m1 = m - m2;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m1; j++) {
            h[i] <<= 1;
            h[i] += (c[i][j] == '*');
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m2; j++) {
            h[n + i] <<= 1;
            h[n + i] += (c[i][m1 + j] == '*');
        }
    }

    int im1 = 1 << m1;
    for (int i = 0; i < im1; i++) {
        v[0][i] = ones(i, m1);
        for (int j = 0; j < n; j++)
            rm[0][i] = (rm[0][i] << 1) + ((h[j] & (~i)) > 0);
    }

    int im2 = 1 << m2;
    for (int i = 0; i < im2; i++) {
        v[1][i] = ones(i, m2);
        for (int j = 0; j < n; j++)
            rm[1][i] = (rm[1][i] << 1) + ((h[n + j] & (~i)) > 0);
    }

    for (int i = 0; i < im1; i++) {
        int vert = v[0][i];
        int hor = rm[0][i];
        for (int j = 0; j < im2; j++) {
            ans = min(ans, max(v[1][j] + vert, ones(hor | rm[1][j], 31)));
        }
    }

    printf("%d", ans);

    return 0;
}