p527.ans1
======================
2

=================
p527.ans2
======================
0

=================
p527.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;
vector<string> tbl;

void read() {
    cin >> n >> m;
    tbl.resize(n);
    cin >> tbl;
}

void solve() {
    // Each bomb clears one full row and one full column at once, so if a plan
    // bombs r distinct rows and c distinct columns we can pair them up and only
    // need max(r, c) bombs. We enumerate every subset i of the n rows that we
    // choose to bomb: those rows are cleared completely, and the rocks in the
    // remaining rows must be killed by bombing their columns. mask[s] holds the
    // union (bitmask over columns) of rock columns across the rows in set s,
    // built by SOS-style merging of single-row masks. For each chosen row set i
    // the needed columns are mask of the complement, and the cost is
    // max(popcount(rows), popcount(columns)); we minimise this over all subsets.

    vector<int> mask(1 << n, 0);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(tbl[i][j] == '*') {
                mask[1 << i] |= 1 << j;
            }
        }
    }

    for(int i = 1; i < (1 << n); i++) {
        int l = i & -i;
        mask[i] = mask[l] | mask[i ^ l];
    }

    int ans = n + m;
    for(int i = 0; i < (1 << n); i++) {
        int mask_m = mask[((1 << n) - 1) ^ i];
        ans = min(ans, max(__builtin_popcount(i), __builtin_popcount(mask_m)));
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p527.in1
======================
8 10
..........
..***..*.*
.*.......*
.*.......*
.*.......*
.....*****
..........
.........*

=================
p527.in2
======================
3 4
....
....
....

=================
statement.txt
======================
527. Explode 'Em All
Time limit per test: 1.5 second(s)
Memory limit: 524288 kilobytes
input: standard
output: standard

The prime minister of Berland decided to build a new city in the country. It's hard to describe the excitement of all Berland citizens, but indeed this is great news from the economic, social and cultural standpoints.

The land in Berland is occupied almost entirely and it's very hard to find free space for construction, so it was decided to build the city on a stony terrain. The map of this terrain is represented as an nx m grid, where each cell of the grid is either an empty space or a rock.

Of course, before construction is started, the given terrain must be completely cleared from rocks. As you may guess, you were hired to complete this mission. Your goal is to destroy all rocks by dropping bombs from a plane. A bomb can be dropped on any cell of the map, and you are free to select where you want to drop each bomb. When a bomb targeted for cell (i, j) reaches the ground, it destroys all rocks in row i and also all rocks in column j of the grid. If cell (i, j) contains a rock, this rock is also destroyed.

Please help the prime minister of Berland to find the minimum number of bombs required to completely clear the given terrain from rocks.

Input
The first line of input contains two integers n and m (1 ≤ n,m ≤ 25) — the number of rows and columns correspondingly. Each of the next n lines contains m characters describing the terrain. An empty space is denoted by ".", while a rock is denoted by "*".

Output
Write a single integer to the output — the minimum numbers of bombs required for destroying all rocks on the terrain.

Example(s)
sample input
sample output
8 10
..........
..***..*.*
.*.......*
.*.......*
.*.......*
.....*****
..........
.........*
2

sample input
sample output
3 4
....
....
....
0



Note
In the first sample test it's only required to drop 2 bombs from a plane: one bomb to cell (2,2) and another bomb to cell (6, 10). Row and column indices in this explanation are 1-based.


=================
