Submission #54579828

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using namespace atcoder;
namespace mp = boost::multiprecision;

using ll = long long;
using pll = pair<ll,ll>;
using bint = mp::cpp_int;
using mint = modint998244353;

ll N, M;
vector<ll> T;
ll ans = 1e17;
ll comp;

void rec(ll i, ll st, ll cnt)
{
  if(st == comp)
  {
    ans = min(ans, cnt);
    return;
  }
  if(i == N)
  {
    return;
  }

  rec(i+1, st|T[i], cnt+1);
  rec(i+1, st, cnt);
}

int main()
{
  cin >> N >> M;
  T.resize(N, 0);

  for(ll i = 0;i < N;i++)
  {
    string S;
    cin >> S;
    for(ll j = 0;j < M;j++)
    {
      if(S[j]=='o')
      {
        T[i] |= 1 << j;
      }
    }
  }
  comp = (1<<M)-1;

  rec(0, 0, 0);

  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result