Educational Codeforces Round 68 (Rated for Div. 2) B. Yet Another Crosses Problem

B. Yet Another Crosses Problem

https://codeforces.com/contest/1194/problem/B

함정이 숨겨진 구현 문제.

row와 col이 교차하는 것이 1개라도 있도록 블록을 채워넣는 문제이다.

다시말해 전부 칠해진 행과 열이 각각 한개 이상씩 있게 해야 한다.

n x m이 40만개밖에 안된다.

각 행에서 가득 차려면 더 채워야 하는 블록의 개수와, 각 열에서 더 채워야 하는 블록의 개수를 저장하자.

전체를 탐색하면서 '.'인 경우에 해당 row와 col에 저장된 채워야 하는 개수를 합하고 1을 뺀다.

'*'인 경우에 해당 row와 col에 저장된 채워야 하는 개수를 합한다.

이 과정들에서 가장 최소의 값을 찾아 출력하자.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define rep(i, a, b) for(ll i=a; i<=b; i++)
ll gcd(ll a, ll b) { while (b) { a %= b, swap(a, b); }    return a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
#define MAXN 50050
#define PI 3.14159265358979323846
#define MOD 1000000000
 
ll n, m, k;
ll a, b, c;
ll rownum[MAXN], colnum[MAXN];
string s[MAXN];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    
    rep(test, 1, t) {
        cin >> n >> m;
        
        rep(i, 0, n - 1) rownum[i] = 0;
        rep(i, 0, m - 1) colnum[i] = 0;
        
        ll minv = 1e9;
 
        rep(i, 0, n - 1) {
            cin >> s[i];
            rep(j, 0, m - 1) {
                if (s[i][j] == '.') {
                    rownum[i]++, colnum[j]++;
                }
            }
        }
        
        rep(i, 0, n - 1) rep(j, 0, m - 1) {
            if (s[i][j] == '.') {
                if (minv > rownum[i] + colnum[j] - 1) {
                    minv = rownum[i] + colnum[j] - 1;
                }
            }
            else minv = min(minv, rownum[i] + colnum[j]);
        }
 
        cout << minv << '\n';
    }
    
    return 0;
}