Untitled

#include <iostream>
#include <vector>
#include <string>
#include <climits>
#include <cstdlib>
#include <ctime>
using namespace std;

void solve() {
    int q;
    cout << "Enter the number of test cases: ";
    cin >> q; // Number of test cases

    srand(time(0)); // Seed the random number generator

    while (q--) {
        int n, m;
        cout << "Enter dimensions (n m): ";
        cin >> n >> m; // Dimensions of the grid

        // Generate a random grid
        vector<string> grid(n);
        cout << "Generating a random grid:" << endl;
        for (int i = 0; i < n; ++i) {
            string row;
            for (int j = 0; j < m; ++j) {
                row += (rand() % 2 == 0) ? '.' : '*'; // Randomly choose between '.' and '*'
            }
            grid[i] = row;
        }

        // Display the randomly generated grid
        cout << "Random Grid:" << endl;
        for (int i = 0; i < n; ++i) {
            cout << grid[i] << endl;
        }

        // Step 1: Precompute the number of black cells (*) in each row and column
        vector<int> row_black_count(n, 0);
        vector<int> col_black_count(m, 0);

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == '*') {
                    row_black_count[i]++;
                    col_black_count[j]++;
                }
            }
        }

        // Step 2: Calculate the minimum effort to create a cross
        int min_effort = INT_MAX;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                // Calculate the number of cells to paint
                int current_effort = (m - row_black_count[i]) + (n - col_black_count[j]);
                if (grid[i][j] == '.') {
                    // Avoid double-counting if the current cell is white
                    current_effort -= 1;
                }

                min_effort = min(min_effort, current_effort);
            }
        }

        // Output the result for this test case
        cout << "Minimum minutes to make the grid interesting: " << min_effort << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}