Consider deciding for each shop whether to visit there or not. There are \(2^N\) choices of shops, which is no more than about \(10^3\) under the constraints of this problem, so we can try all of them easily. Specifically, for each choice of shops to visit, check if that choice covers all the flavors, and if it does, update \(\mathrm{ans} \leftarrow \min(\mathrm{ans},x)\).

All that left is implementation. As in our problem, when it comes to brute-forcing all \(2^N\) combinations of choosing some of \(N\) items, the technique called bitwise enumeration is widely used due to its simple implementation. In this trick, “choosing \(k\) items \(x_1,x_2\dots,x_k\) out of \(N\) items numbered \(0,1,\dots,N-1\)” is corresponded to “an integer whose \(x_1,x_2,\dots,x_k\)-th bit is set in its binary representation.” This way, the \(2^N\) choices out of \(N\) items correspond one-to-one to an integer between \(0\) and \(2^N-1\) (inclusive). Thus, instead of enumerating the choices, we can enumerate the integers (which is achieved by an easy for statement).

In order to reconstruct the choice from an integer, one needs to find the \(k\)-th digit of the binary representation of \(x\), given integers \(x\) and \(k\). Most languages provide bitwise operations, which facilitate the implementation of this operation. For details, refer to the sample code below.

Sample code (C++):

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    int ans = n;
    for (int bit = 0; bit < (1 << n); bit++) {
        vector<bool> exist(m);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (bit >> i & 1) {
                ++cnt;
                for (int j = 0; j < m; j++) {
                    if (s[i][j] == 'o') exist[j] = true;
                }
            }
        }
        bool all_exist = true;
        for (int j = 0; j < m; j++) {
            if (!exist[j]) all_exist = false;
        }
        if (all_exist) ans = min(ans, cnt);
    }
    cout << ans << endl;
}