Untitled
unknown
plain_text
5 months ago
2.3 kB
5
Indexable
#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; }
Editor is loading...
Leave a Comment